（LeetCodeHot100）64. 最小路径和——minimum-path-sum

64. 最小路径和——minimum-path-sum

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

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

示例 1：

img

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

示例 2：

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid.length; // n是列
        int m = grid[0].length; // m是行
        int[][] ans = new int[m][n];
        ans[0][0] = grid[0][0];
        // 第一行可以先确定下来
        for (int i = 1; i < m; i++) {
            ans[0][i] = grid[0][i] + grid[0][i-1];
        }
        // 第一列可以先确定下来
        for (int i = 1; i < n; i++) {
            ans[i][0] = grid[i][0] + grid[i-1][0];
        }
        // 将其余的数先设为整数最大数
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                ans[i][j] = Integer.MAX_VALUE;
            }
        }
        // 得到最小的路径
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                ans[i][j] = Math.min(ans[i][j], ans[i-1][j] + ans[i][j-1]);
            }
        }
        return ans[m-1][n-1];
    }
}
  • 我知道为什么错了：因为我以为跟上一题一样，其实不然→上一题是路径种数，是要把左边的和上面的相加，但是这一题是求最短路径，是左边的和上面的小的那个跟自己相加，放到自己的这个位置上
  • 还有要注意的是求二维数组的行数和列数：
    • matrix.length是行数，因为二维数组是一维数组的数组
    • matrix[0].length是列数，相当于matrix[0]是第一行，相当于一个数组

1. 行列定义修正

  • 原错误：int n = grid.length; int m = grid[0].length;（颠倒了行列）

  • 修正后：

    1
    int m = grid.length; int n = grid[0].length;

    例：输入[[1,3,1],[1,5,1],[4,2,1]]，m=3（3 行），n=3（3 列），dp 数组维度为 3x3（与原网格一致）。

2. 第一行 / 第一列初始化修正

  • 原错误：

    1
    ans[0][i] = grid[0][i] + grid[0][i-1]

    比如第一行[1,3,1]，按原逻辑会计算为1, 3+1=4, 1+3=4，但正确路径和是 1, 1+3=4, 4+1=5（用前一个路径和累加）。

  • 修正后：dp[0][j] = grid[0][j] + dp[0][j-1]，确保累加的是「已计算的最小路径和」。

3. 状态转移方程修正

  • 原错误：

    1
    ans[i][j] = Math.min(ans[i][j], ans[i-1][j] + ans[i][j-1])

    这个逻辑完全错误，相当于把「上方和左方的路径和相加」，而非取最小值后加自身。

  • 修正后：

    1
    dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1])

    解释：到达(i,j)只能从(i-1,j)（上方）或(i,j-1)（左方）来，取两者中路径和较小的那个，再加上当前单元格的值，就是当前的最小路径和。

正确答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length; // m是行
        int n = grid[0].length; // n是列
        // 第一行可以先确定下来
        for (int i = 1; i < n; i++) {
            grid[0][i] = grid[0][i] + grid[0][i-1];
        }
        // 第一列可以先确定下来
        for (int i = 1; i < m; i++) {
            grid[i][0] = grid[i][0] + grid[i-1][0];
        }
        // 得到最小的路径
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}

官方题解

跟我的一样的

方法一：动态规划

由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。

对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。

创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。

  • 当 i > 0 且 j = 0 时：dp[i][0] = dp[i−1][0] + grid[i][0]
  • 当 i = 0 且 j > 0 时：dp[0][j] = dp[0][j−1] + grid[0][j]
  • 当 i > 0 且 j > 0 时：dp[i][j] = min(dp[i−1][j], dp[i][j−1]) + grid[i][j]

最后得到 dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
}

复杂度分析

  • 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 dp 的每个元素的值。
  • 空间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。创建一个二维数组 dp*，和网格大小相同。
    空间复杂度可以优化，例如每次只存储上一行的 *dp     值，则可以将空间复杂度优化到 O(n)。