最小路径和
Minimum Path Sum
在非负整数网格中从左上角走到右下角，每次只能向下或向右，求路径上的最小数字和。
在力扣中练习题目描述
给定一个包含非负整数的 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.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
解题思路
二维 DP · 累计路径和
到达每格的最小和，等于两条来路中较小的那个再加上当前格
路径总数是指数级的，逐条比较不可行。但到达 (i,j) 的最后一步仍然只有两种：从上面下来，或从左边过来。
设 dp[i][j] 为到达该格的最小路径和：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
注意选择的是来源的累计和，最后才把当前格的值加上去，而不是先加再比较。
自拟主例的网格第一行是 3,1,4,2，第一列是 3,2,4；它们没有选择，只能一路累加。内部格子才开始出现两条来路，例如 (2,2) 从上方 9+6=15、从左方 11+6=17 中取 15。
(1,1)：从上方来是 4 + 5 = 9，从左方来是 5 + 5 = 10，取 9。
- i
- 1
- j
- 1
dp[i][j]：从左上角走到 (i,j) 的最小路径和
dp[1][1]=min(dp[0][1] + grid[1][1], dp[1][0] + grid[1][1])min(4 + 5, 5 + 5)=9选中 dp[0][1] 从上方
边界是累加而不是全 1：dp[i][0] = dp[i-1][0] + grid[i][0]，第一行同理。
(2,2)：从上方来是 9 + 6 = 15，从左方来是 11 + 6 = 17，取 15。
- i
- 2
- j
- 2
dp[i][j]：从左上角走到 (i,j) 的最小路径和
dp[2][2]=min(dp[1][2] + grid[2][2], dp[2][1] + grid[2][2])min(9 + 6, 11 + 6)=15选中 dp[1][2] 从上方
时间 O(m × n)，空间 O(m × n)。
易错点
- 先比较 grid 本身而不是 dp：路径和是累计量，必须比较到达来源的累计和。
- 边界也初始化为 1：第一行/第一列只能单向累加，值并不相等。
- 忘记加 grid[i][j]：只取了来源的较小值，当前格被漏掉。
滚动数组 · 一维 DP
一行一行覆盖，dp[j] 覆盖前是上方，dp[j-1] 是本行左方
时间相同，空间从 O(m × n) 降到 O(n)；代价是无法直接回溯路径，需要额外记录来源。
转移只依赖上一行和本行左边，所以保留一行就够。
每行开始时，dp[0] 要先加上当前行第一列的 grid[i][0]，因为第一列只能从上方来。然后 j 从左往右：
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
此时 dp[j] 还没被覆盖，是上一行的上方值；dp[j-1] 已经更新，是本行左方值。
时间 O(m × n)，空间 O(n)。
- 1dp[0] = grid[0][0]，第一行累加。
- 2每行先更新 dp[0] += grid[i][0]。
- 3j 从左到右：dp[j] = min(dp[j], dp[j-1]) + grid[i][j]。
- 4返回 dp[n-1]。
易错点
- 忘记更新 dp[0]：第一列的累计和还停留在第一行。
- j 从右往左：dp[j-1] 还是上一行的值，左方来源用错。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
grid = [[3,1,4,2],[2,5,1,3],[4,2,6,1]]从 (0,0) 的 3 开始；第一行只能向右累加，第一列只能向下累加。
- m × n
- 3 × 4
dp[i][j]：从左上角走到 (i,j) 的最小路径和
dp[0][0]=3查看 C++ 代码
延伸阅读
- 和不同路径的区别只有转移里的运算符：路径数用加法，最小路径和先取 min 再加当前格。
- 若格子允许负数，这个 DP 仍然成立；但“只能向右/向下”的无环性质是它成立的前提。