LeetCode 64：最小路径和（Minimum Path Sum）题解

Minimum Path Sum 是 LeetCode Hot 100 里面一道非常经典的动态规划题。

这道题和前面的“不同路径”非常像，都是网格类问题，也都是从左上角走到右下角。 但两道题的目标并不一样：

• “不同路径”是在问一共有多少种走法

• “最小路径和”是在问所有合法路径中，路径数字和最小是多少

也正因为如此，这道题虽然表面上还是“网格移动”，但思维重点已经从“计数”变成了“最优值转移”。

你给出的这份 Java 代码，使用的是这道题最经典的一种解法：

动态规划 + 原地修改

它的核心思想非常清晰：

• 到达某个格子的最小路径和，只可能来自它的上方或者左方

• 所以当前格子的最优值，就是当前值加上这两个来源中的较小者

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

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

注意机器人每次只能向下或者向右移动一步。

也就是说，从任意一个位置 (i, j) 出发，你只能：

• 向右走到 (i, j + 1)

• 向下走到 (i + 1, j)

最终要求的是：

从 (0,0) 到 (m-1,n-1) 的所有合法路径中，路径和最小的那个值。

示例

示例 1

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

因为最优路径是：

1 → 3 → 1 → 1 → 1

路径和为：

1 + 3 + 1 + 1 + 1 = 7

示例 2

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

最优路径是：

1 → 2 → 3 → 6

路径和为：

12

最直接的想法是什么？

如果最开始不考虑效率，很多人可能会想到：

• 从左上角开始递归

• 每次尝试向右走或者向下走

• 枚举所有合法路径

• 计算每条路径的和

• 最后取最小值

这个思路当然是对的，但问题在于：

• 路径数量很多

• 会出现大量重复计算

• 同一个格子往后的最优结果会被反复求很多次

所以暴力递归效率很差。

而这类“从左上走到右下、每步只有有限选择”的网格题，通常都非常适合用动态规划。

核心思路：动态规划

这道题最关键的问题是：

到达某个位置 (i, j) 的最小路径和，应该怎么表示？

我们可以定义：

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

那么对于任意位置 (i, j)，因为只能从上方或左方走过来，所以：

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

这就是整道题最核心的状态转移方程。

但要注意，这个公式只适用于既不是第一行、也不是第一列的位置。 因为第一行只能从左边来，第一列只能从上边来。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    public int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 起点不需要处理
                if (i == 0 && j == 0) continue;

                // 第一行：只能从左边走过来
                if (i == 0) {
                    grid[i][j] += grid[i][j - 1];
                }
                // 第一列：只能从上边走过来
                else if (j == 0) {
                    grid[i][j] += grid[i - 1][j];
                }
                // 其他位置：取上方和左方中的较小值
                else {
                    grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
                }
            }
        }

        return grid[grid.length - 1][grid[0].length - 1];
    }
}

代码拆解

这段代码的结构很简洁，而且它没有额外开一个 dp 数组，而是直接在原数组 grid 上修改。 这其实是一种很常见的空间优化写法。

下面一步一步来看。

1. 为什么这题适合动态规划？

因为到达某个格子的最优值，依赖于它前面的最优值。

对于位置 (i, j) 来说：

• 如果最后一步是从上面走下来，那它来自 (i - 1, j)

• 如果最后一步是从左边走过来，那它来自 (i, j - 1)

所以当前格子的最小路径和，不需要去考虑所有历史路径，只需要看：

• 上面的最小路径和

• 左边的最小路径和

这就满足了动态规划的典型特征：

• 最优子结构

• 重复子问题

2. 为什么起点不用处理？

if (i == 0 && j == 0) continue;

因为左上角是起点，本身就是路径的开始。 从起点到起点的最小路径和当然就是它自己的值：

grid[0][0]

所以不需要再做任何转移。

3. 为什么第一行只能从左边来？

if (i == 0) {
    grid[i][j] += grid[i][j - 1];
}

因为题目规定只能向右或向下走。

如果当前位置在第一行，比如 (0, j)，那么它上面根本没有格子，所以不可能从上边来。 唯一可能的来源就是左边 (0, j - 1)。

因此第一行的状态转移只能是：

dp[0][j] = grid[0][j] + dp[0][j-1]

这也很好理解： 第一行从左到右走，本质上只有一条路。

4. 为什么第一列只能从上边来？

else if (j == 0) {
    grid[i][j] += grid[i - 1][j];
}

同理，如果当前位置在第一列，比如 (i, 0)，它左边没有格子，所以不可能从左边来。 唯一可能的来源就是上边 (i - 1, 0)。

因此第一列的状态转移是：

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

这也说明第一列同样只有一条固定路径。

5. 为什么普通位置要取 min(grid[i][j-1], grid[i-1][j])？

else {
    grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
}

因为当前位置 (i, j) 有两个可能来源：

• 左边 (i, j - 1)

• 上边 (i - 1, j)

而我们要求的是“最小路径和”，所以当然应该选这两个来源中路径和较小的那个。

因此状态转移就是：

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

这一步就是整道题的核心。

6. 为什么直接修改 grid 也可以？

这段代码没有额外写：

int[][] dp = new int[m][n];

而是直接在 grid 上修改：

grid[i][j] += ...

这是因为当我们遍历到 (i, j) 时：

• grid[i][j - 1] 已经被更新成“到达左边格子的最小路径和”

• grid[i - 1][j] 也已经被更新成“到达上边格子的最小路径和”

所以原数组本身已经可以兼作 dp 数组使用。

换句话说：

遍历过程中，grid[i][j] 的含义已经从“原始数字”变成了“到达这里的最小路径和”。

这就是空间优化的关键。

手动模拟一遍

我们用经典例子来走一遍：

grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

初始状态

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

处理第一行

(0,1)

只能从左边来：

3 + 1 = 4

更新后：

[
  [1,4,1],
  [1,5,1],
  [4,2,1]
]

(0,2)

只能从左边来：

1 + 4 = 5

更新后：

[
  [1,4,5],
  [1,5,1],
  [4,2,1]
]

处理第二行

(1,0)

只能从上边来：

1 + 1 = 2

更新后：

[
  [1,4,5],
  [2,5,1],
  [4,2,1]
]

(1,1)

可从左边或上边来：

• 左边：2

• 上边：4

取较小值 2：

5 + 2 = 7

更新后：

[
  [1,4,5],
  [2,7,1],
  [4,2,1]
]

(1,2)

• 左边：7

• 上边：5

取较小值 5：

1 + 5 = 6

更新后：

[
  [1,4,5],
  [2,7,6],
  [4,2,1]
]

处理第三行

(2,0)

只能从上边来：

4 + 2 = 6

更新后：

[
  [1,4,5],
  [2,7,6],
  [6,2,1]
]

(2,1)

• 左边：6

• 上边：7

取较小值 6：

2 + 6 = 8

更新后：

[
  [1,4,5],
  [2,7,6],
  [6,8,1]
]

(2,2)

• 左边：8

• 上边：6

取较小值 6：

1 + 6 = 7

最终得到：

[
  [1,4,5],
  [2,7,6],
  [6,8,7]
]

右下角的值 7 就是最小路径和。

为什么这个方法是正确的？

因为到达每个位置的路径，最后一步一定来自：

• 上边

• 或左边

而这两个方向之外没有第三种可能。

所以如果我们已经知道：

• 到达上边格子的最小路径和

• 到达左边格子的最小路径和

那么当前位置的最优值一定就是：

当前格子值 + min(上方最优值, 左方最优值)

这正是动态规划的标准思想：

当前最优解建立在更小子问题的最优解之上。

所以这个状态转移是完全正确的。

复杂度分析

时间复杂度

我们遍历了整个网格一次，每个格子只处理一次，所以时间复杂度是：

O(m × n)

空间复杂度

由于直接在原数组 grid 上修改，没有额外开二维 dp 数组，所以额外空间复杂度是：

O(1)

如果不允许修改原数组，那么一般会写成 O(m × n) 的额外空间。 而你这份代码正好做到了空间优化。

这道题真正想考什么？

这道题表面上是在求最小路径和，但本质上考察的是网格型动态规划的基本功。

第一，是否能正确定义状态

你必须明确：

grid[i][j] / dp[i][j]

到底表示什么。

在这题里，它表示的是：

从起点走到当前位置的最小路径和

只要状态定义清楚，后面的转移就会很自然。

第二，是否能处理好边界

这题里最容易写错的地方，其实不是一般位置，而是：

• 起点

• 第一行

• 第一列

因为这些位置的来源不完整，不能直接套统一公式。

第三，是否能做空间优化

很多人写动态规划时，会习惯性新开一个 dp 数组。 但这题其实可以直接在原网格上更新，这也是一个非常值得掌握的小技巧。

和“不同路径”有什么区别？

这两题都是网格题，很容易一起记。

不同路径

问的是：

到达终点一共有多少种走法

状态转移是：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

最小路径和

问的是：

到达终点的最小代价是多少

状态转移是：

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

所以两道题的网格结构一样，但一个是“加法计数”，一个是“取最小值”。

这是网格 DP 题里非常典型的两种模型。

总结

这道题的核心思想可以概括成一句话：

到达每个格子的最小路径和，只可能来自它的上方或左方，因此当前最优值就是当前格子值加上这两个来源中的较小者。

具体步骤就是：

1. 从左上到右下遍历整个网格

2. 起点保持不变

3. 第一行只能从左边转移

4. 第一列只能从上边转移

5. 其他位置取：

当前值 + min(左边最优值, 上边最优值)

6. 最终右下角的值就是答案

这样就能在：

O(m × n)

的时间复杂度和：

O(1)

的额外空间复杂度下解决问题。

这是一道非常经典、也非常值得反复理解的动态规划题。 因为它会让你真正体会到：

• 网格类问题为什么常常适合 DP

• 最优值问题和计数问题在状态转移上的区别

• 原地修改为什么可以作为一种有效的空间优化

把这道题真正吃透之后，再去看：

• 不同路径 II

• 三角形最小路径和

• 地下城游戏

• 礼物的最大价值

这些网格或路径类 DP 题时，你会明显更容易抓住套路。

因为“最小路径和”本身就是网格动态规划里非常经典的一道模板题。