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] <= 200

思路

1. 初始化：
   创建一个 dp 数组，大小与 grid 一致。
   初始化 dp[0][0] 为 grid[0][0]，表示从起点到起点的路径总和。

2. 初始化第一行和第一列：
   对于第一行，路径只能从左边来，因此 dp[0][j] = dp[0][j - 1] + grid[0][j]。
   对于第一列，路径只能从上面来，因此 dp[i][0] = dp[i - 1][0] + grid[i][0]。

3. 建立状态转移方程：
   如果 i == 0 且 j == 0，那么 dp[i][j] = grid[i][j]。
   如果 i == 0，那么 dp[i][j] = dp[i][j - 1] + grid[i][j]。
   如果 j == 0，那么 dp[i][j] = dp[i - 1][j] + grid[i][j]。
   对于其他位置，dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。

4. 填充 dp 表：
   从 dp[1][1] 开始，遍历整个 dp 表。
   每个位置 (i, j) 的值等于从上方或左方路径中的较小值加上当前位置的值，即 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。

5. 返回结果：
   返回 dp[m-1][n-1]，即从起点到终点的路径上的数字总和最小值。

• 时间复杂度:O(mn)
• 空间复杂度:O(mn)

代码

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];
    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++) {
            // 每个位置(i, j)的值等于从上方或左方路径中的较小值加上当前位置的值
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[m - 1][n - 1];
}