Hot 100 --- 最小路径和

本文概览：本文讲解最小路径和的核心思路：只能向下或向右移动时，到达每个格子的最小路径和有且仅有上方和左方两个来源取较小值，用动态规划递推；与不同路径同结构，差别只在状态含义与初始化，方法二用一维数组滚动到 O(n) 空间

一、题目

二、题目分析

1. 题目要求

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

示例：grid = [[1,3,1],[1,5,1],[4,2,1]] → 7

路径 1 → 3 → 1 → 1 → 1 总和为 7。

2. 怎么想这题？

和上一题《不同路径》是同一张网：只能向下或向右，所以到达任意一个格子 (i, j)，只有两个来源——从正上方 (i-1, j) 下来一步，或从正左方 (i, j-1) 走过来一步，没有第三种。

区别在这题要的是"数字总和最小"。那站在 (i, j) 往回看：不管从哪条路来，想让它到这儿的累计和最小，就选"(i-1, j) 的最小路径和"和"(i, j-1) 的最小路径和"里较小的那个，再加上 grid[i][j] 本身。(i, j) 只关心到达它上面和左边两个格子各自的最优值，不用管它们具体怎么走的——这又是动态规划的"无后效性"。

和上一题的区别只在一个地方：状态存的是什么、初始化怎么填。上一题存"路径条数"，边界是"第一行第一列全 1"；这题存"最小路径和"，边界来自"第一行只能从左来、第一列只能从上走"，不能随便填 1。

3. 需要解决哪几个问题？

问题一：状态怎么定义？dp[i][j] 表示什么？

问题二：转移方程怎么写？到达 (i, j) 的最小和，由哪几个已知值推出来？

问题三：第一行和第一列怎么初始化？这两处的来源只有一个，能不能直接套转移方程？

三、方法一：二维 DP 数组，O(m × n) 空间

1. 思路概览

public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][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++) {
dp[i][0] = dp[i – 1][0] + grid[i][0];
}
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];
}

思路简要说明：

2. 思路详解

第一步：解决状态定义——dp[i][j] 表示什么？

题目要的是"从左上角到右下角的最小路径和"。照样把状态安在每个格子上：

dp[i][j] = 从 (0,0) 走到格子 (i,j) 的最小数字总和。

答案就是 dp[m-1][n-1]。

第二步：解决转移方程——为什么取 min 还要加自身？

这两个来源对应两条真实的三路，走任何一条到 (i,j)：从上方来，累计和是 dp[i-1][j]，再踩上 grid[i][j]；从左方来，累计和是 dp[i][j-1]，再踩上 grid[i][j]。要最小，两个里挑小的那把：

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

注意和上一题不同：上一题是 +（路径条数相加），这题是 min（挑一条路）+ grid[i][j]。因为每个格子自身的数字必须算进总和里。

第三步：解决边界——第一行、第一列为什么不能用转移方程？

转移方程要读 dp[i-1][j] 和 dp[i][j-1] 两个值再取 min。但：

• 第一行（i = 0）：没有上方格子 dp[-1][j]，它只能从一个来源来——从左边的格子"向右"走。所以 dp[0][j] 得单独累加：dp[0][j] = dp[0][j-1] + grid[0][j]，一路把前缀和加起来。
• 第一列（j = 0）：没有左方格子 dp[i][-1]，只能从一个来源来——从上边的格子"向下"走。所以 dp[i][0] = dp[i-1][0] + grid[i][0]。
• 起点（(0,0)）：不走也有它自己这一格，dp[0][0] = grid[0][0]。

如果 (0,0) 也套转移方程，会读到两个不存在的格子；而第一行、第一列若搞一个统一的初始值，就丢了"只能沿一条边往下/往右累加"这个事实。所以边界必须单独初始化，而不是像上题那样全填 1。

这也就是题目分析里"问题三"的答案：第一行、第一列来源唯一，必须先独立累加初始化。

第四步：完整执行过程

以示例网格为例：

grid:
1 3 1
1 5 1
4 2 1

初始化：
dp[0][0] = 1
第一行：dp[0][1] = 1+3 = 4，dp[0][2] = 4+1 = 5
第一列：dp[1][0] = 1+1 = 2，dp[2][0] = 2+4 = 6

0 1 2
0 [ 1 4 5 ]
1 [ 2 . . ]
2 [ 6 . . ]

i=1, j=1：min(dp[0][1], dp[1][0]) = min(4,2) = 2，+5 = 7
i=1, j=2：min(dp[0][2], dp[1][1]) = min(5,7) = 5，+1 = 6

0 1 2
0 [ 1 4 5 ]
1 [ 2 7 6 ]
2 [ 6 . . ]

i=2, j=1：min(dp[1][1], dp[2][0]) = min(7,6) = 6，+2 = 8
i=2, j=2：min(dp[1][2], dp[2][1]) = min(6,8) = 6，+1 = 7

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

返回 dp[2][2] = 7 ✓（对应 1→3→1→1→1）

3. 复杂度分析

时间复杂度 O(m × n)：每个格子常数次运算。

空间复杂度 O(m × n)：完整的二维 dp 表。

四、能不能也用一维数组省空间？

和上题一样，转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 只依赖两个值：正上方的 dp[i-1][j] 和正左方的 dp[i][j-1]。算完一行，上一行就没用了，两行可以挤进同一个一维数组。上一题滚动靠 row[j] += row[j-1]（一条路够了不必取 min），这一题要取 min，滚动写法关键的差别在于每一行的 row[0] 不能继续用旧的 1，得先自主更新。

五、方法二：一维数组滚动，O(n) 空间

1. 思路概览

public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] row = new int[n];
row[0] = grid[0][0];
// 先初始化第一行（只能从左累加）
for (int j = 1; j < n; j++) {
row[j] = row[j – 1] + grid[0][j];
}
// 从第二行开始逐行递推
for (int i = 1; i < m; i++) {
row[0] += grid[i][0]; // 每一行第一列自主更新（只能从上累加）
for (int j = 1; j < n; j++) {
row[j] = Math.min(row[j], row[j – 1]) + grid[i][j];
}
}
return row[n – 1];
}

思路简要说明：

2. 思路详解

第一步：初始化为什么先填第一行？

一维 row 对应"当前行"。循环从 i = 1 开始，进入前 row 得先装好第一行。第一行只能从左累加，于是：

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

这行代码和方法一里 dp[0][j] 的初始化一模一样。

第二步：为什么每一行的开头要先更新 row[0]？

滚动数组的坑在这。进入第 i 行时，row[0] 还留着上一行第 0 列的值（上一轮算出来的）。但第一列（j = 0）只能从上方走来，所以第 i 行的 row[0] 应该等于"上一行的 row[0] + grid[i][0]"。

如果不更新，row[0] 就卡在旧的第一行值上，后面算 row[1] 要用它当"左方值"就错了。所以每进一行先执行：

row[0] += grid[i][0]

第三步：row[j] = min(row[j], row[j-1]) + grid[i][j] 在算啥？

进入第 i 行的内层循环时，row 里同时躺着两层信息：

• row[j] 此刻还是上一行同列 dp[i-1][j] 的最小路径和，也就是"上方"那份；
• row[j-1] 已经在本轮改成本行 j-1 列的新值，也就是"左方"那份。

取二者较小，再踩上当前格子的 grid[i][j]，写回 row[j]——把"上方"和"左方"两条路compare后选小，正好等价于方法一的转移方程。覆盖后 row[j] 只剩本行的新值，数组始终只保留一行。

对比上一题：上一题 l22 row[j] += row[j-1] 是直接把左方值加到上方值上；这题因为各自格子数字要参与、还要取 min，写成 Math.min(row[j], row[j-1]) + grid[i][j]。其他完全相同。

第四步：完整执行过程

grid:
1 3 1
1 5 1
4 2 1

初始化第一行：
row[0]=1
row[1]=1+3=4，row[2]=4+1=5 → row=[1, 4, 5]

i=1（第二行）：
row[0] += grid[1][0] = 1+1 = 2 → [2, 4, 5]
j=1：min(row[1], row[0]) + grid[1][1] = min(4,2) + 5 = 7 → [2, 7, 5]
j=2：min(row[2], row[1]) + grid[1][2] = min(5,7) + 1 = 6 → [2, 7, 6]

i=2（第三行）：
row[0] += grid[2][0] = 2+4 = 6 → [6, 7, 6]
j=1：min(row[1], row[0]) + grid[2][1] = min(7,6) + 2 = 8 → [6, 8, 6]
j=2：min(row[2], row[1]) + grid[2][2] = min(6,8) + 1 = 7 → [6, 8, 7]

返回 row[2] = 7 ✓

每一轮的 row，正好对应方法一二维表里那一行的取值，滚到最后一行，row[n-1] 就是答案。

3. 复杂度分析

时间复杂度 O(m × n)：两层循环规模不变。

空间复杂度 O(n)：只留一行，从 O(m × n) 降到 O(n)。

六、总结

两道题共用同一套思路骨架：只能向下或向右，决定了到达每个格子只有上方、左方两个来源。差别全在两个字——上一题问"有几条"，于是状态是条数、转移是求和、边界全 1；这题问"最小和是多少"，于是状态是最小和、转移是取 min 再叠加自身、边界是"来源唯一所以必须独立累加"。

如果一开始就直接套上一题的模板把第一行第一列全填 1，会犯一个典型错误：dp[0][0] 凭空被赋成 1，丢掉 grid[0][0]，后面所有格子都被污染。先想清楚"每个位置的最小和只能由哪个来源得到"，再定初始化，就顺了。