LeetCode题解：最小路径和

题目描述

给定一个包含非负整数的m×n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

方法思路

由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。
对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。
除了左边界与上边界的网格，每个网格的值都来自于左边和上边中的网格最小值加上该网格的值，所以状态变化方程为：dp[i][j]=Math.min(dp[i-1][j]，dp[i][j-1])+grid[i][j]

class Solution {
    public int minPathSum(int[][] grid) {
        if(grid==null||grid.length==0||grid[0].length==0){
            return 0;
        }
        int row = grid.length,column = grid[0].length;
        int[][] dp = new int[row][column];
        //创建等大表格
        dp[0][0] = grid[0][0];
        //填充第一列
        for(int i=1;i<row;i++){
            dp[i][0] = dp[i-1][0]+grid[i][0];
        }
        //填充第一行
        for(int j=1;j<column;j++){
            dp[0][j] = dp[0][j-1]+grid[0][j];
        }
        //填充其余表格，由于是只能向下或向右移动，所以最小值和来自左或上方
        for(int i=1;i<row;i++){
            for(int j=1;j<column;j++){
                dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        return dp[row-1][column-1];
    }
}

复杂度分析

• 时间复杂度：O(mn)，其中m和n分别是网格的行数和列数。需要对整个网格遍历一次，计算dp的每个元素的值。
• 空间复杂度：O(mn)，其中m和n分别是网格的行数和列数。创建一个二维数组dp，和网格大小相同。