64. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

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

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

动态规划-函数递归+备忘录。

从左上角位置 (0, 0) 走到位置 (i, j) 的最小路径和为 dp(grid, i, j)。结束条件：走到(0,0)，失败条件：越界。查备忘录，递归。

class Solution {
    // 备忘录
    int[][] memo;

    int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 构造备忘录，初始值全部设为 -1
        memo = new int[m][n];
        for (int[] row : memo)
            Arrays.fill(row, -1);
        
        return dp(grid, m - 1, n - 1);
    }

    int dp(int[][] grid, int i, int j) {
        // 结束条件：到达起点
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        // 失败条件：越界检查
        if (i < 0 || j < 0) {
            return Integer.MAX_VALUE;
        }
        // 避免重复计算
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        
        // 状态转移，选择从上方来或从左方来的较小路径和，再加上当前点的值
        memo[i][j] = Math.min(
            dp(grid, i - 1, j),
            dp(grid, i, j - 1)
        ) + grid[i][j];
        return memo[i][j];
    }
}

时间复杂度和空间复杂度都是 O(MN)

动态规划-二维数组迭代

正向遍历，起始点，利用起始点计算第一行和第一列，利用第一行和第一列计算其余的数。

从左上角位置 (0, 0) 走到位置 (i, j) 的最小路径和为 dp[i][j]。

int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];

    // base case：起始点的路径和就是其本身
    dp[0][0] = grid[0][0];
    // 初始化第一列的所有值
    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    // 初始化第一行的所有值
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];        
    
    // 状态转移：遍历每个位置，计算到达该位置的最小路径和
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            // 选择上方或左方的较小路径和，再加上当前点的值
            dp[i][j] = Math.min(
                dp[i - 1][j], // 上方
                dp[i][j - 1]  // 左方
            ) + grid[i][j];
        }
    }

    // 返回到达右下角的最小路径和
    return dp[m - 1][n - 1];
}

• 给定的输入数组 grid 是一个 m x n 的矩阵。
• 代码中包含两层嵌套循环，外层循环遍历行（共 m 行），内层循环遍历列（共 n 列）。
• 每个元素 grid[i][j] 都会被计算一次，计算操作是常数时间的（包括比较、加法和赋值操作）。
• 因此，总的操作次数是 m x n 次。

滚动更新

因为不依赖dp[i-1][j-1]，所以不需要prev

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];

        // 初始化第一行
        dp[0] = grid[0][0];
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        // 遍历每个位置，计算到达该位置的最小路径和
        for (int i = 1; i < m; i++) {
            // 初始化当前行的第一个元素，因为第一个元素只有一种路径可以到达。把j=0和j>=1分开处理，因为0前面没元素
            // 重点。
            dp[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                // dp[j]是上一轮的dp[j]，dp[j-1]是本轮的前一个数字。
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }

        // 返回到达右下角的最小路径和
        return dp[n - 1];
    }
}