LeetCode LCR 099. 最小路径和
目录
题目描述
题意分析
输入一个 $m \times n$ 的非负整数网格，从左上角出发走到右下角，每一步只能向右或向下移动，要求经过的数字总和最小。
「只能向右向下」是最关键的约束：任何一条路径都恰好经过 $m + n - 1$ 个格子，走过的格子不会被再次经过；到达任意格子
(i, j)的上一步只可能来自上方(i - 1, j)或左方(i, j - 1)。数据规模是明确信号：$m, n \le 200$，而从左上到右下的不同路径条数是组合数级别的天文数字，逐条枚举必然超时，必须复用中间结果。
边界上：网格至少 $1 \times 1$；单行只能一路向右、单列只能一路向下，路径唯一；起点和终点的值都要计入总和。
解法：原地动态规划
核心思路
暴力做法是从起点出发递归枚举每一条路径，取最小和。路径条数为 $\binom{m+n-2}{m-1}$，$200 \times 200$ 的网格下完全不可行。
瓶颈在于重复计算：不同路径会反复经过同一个格子，「从起点到这个格子的最优代价」被算了一遍又一遍。观察：到达
(i, j)的最小代价只取决于到上方、到左方两个格子的最小代价中的较小者——前缀具体怎么绕并不影响后续决策。这就是无后效性：只能向右向下，走到(i, j)之后不可能再回头改变之前的格子。于是定义状态
dp[i][j]为从左上角走到(i, j)的最小路径和，转移方程为dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。首行首列必须单独初始化：第一行只能从左边一路走来，
dp[0][j]就是第一行的前缀和；第一列同理是第一列的前缀和。它们只有一个来源，不能套用取min的通用转移。由于每个状态只依赖上方和左方两个已算好的值，可以把结果直接写回
grid本身省掉额外数组——按从左上到右下的顺序遍历时，被覆盖的旧值不会再被用到，原地更新不影响正确性。
解题步骤
- 把第一列累加成前缀和
grid[i][0] += grid[i-1][0]——为什么：第一列的格子只能从上方到达，路径唯一，最小和就是一路累加。- 把第一行累加成前缀和
grid[0][j] += grid[0][j-1]——为什么：同理，第一行的格子只能从左方到达。- 从
(1, 1)开始按行遍历，执行grid[i][j] += min(grid[i-1][j], grid[i][j-1])——为什么：遍历到(i, j)时上方和左方都已经是算好的最小路径和，转移才成立。- 返回
grid[m-1][n-1]——为什么：按状态定义，右下角存的就是全程的最小路径和。- 以
grid = [[1,3,1],[1,5,1],[4,2,1]]走一遍：第一列累加后为1, 2, 6；第一行累加后为1, 4, 5。逐格转移：(1,1) = 5 + min(4, 2) = 7；(1,2) = 1 + min(5, 7) = 6；(2,1) = 2 + min(7, 6) = 8；(2,2) = 1 + min(6, 8) = 7。右下角为7，对应最优路径1 → 3 → 1 → 1 → 1。
代码实现
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int row = 1; row < m; row++) {
grid[row][0] += grid[row - 1][0];
}
for (int col = 1; col < n; col++) {
grid[0][col] += grid[0][col - 1];
}
for (int row = 1; row < m; row++) {
for (int col = 1; col < n; col++) {
// 当前格子只能从上方或左方到达，取较小路径继续。
grid[row][col] += Math.min(grid[row - 1][col], grid[row][col - 1]);
}
}
return grid[m - 1][n - 1];
}
}
func minPathSum(grid [][]int) int {
m := len(grid)
n := len(grid[0])
for row := 1; row < m; row++ {
grid[row][0] += grid[row-1][0]
}
for col := 1; col < n; col++ {
grid[0][col] += grid[0][col-1]
}
for row := 1; row < m; row++ {
for col := 1; col < n; col++ {
// 当前格子只能从上方或左方到达，取较小路径继续。
if grid[row-1][col] < grid[row][col-1] {
grid[row][col] += grid[row-1][col]
} else {
grid[row][col] += grid[row][col-1]
}
}
}
return grid[m-1][n-1]
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子恰好被计算一次，每次转移只做一次比较和一次加法。
- 空间复杂度：$O(1)$，不计输入本身，结果直接覆盖写回原网格，没有额外的状态数组。
关键点总结
- 状态定义先行：
dp[i][j]即「从起点到(i, j)的最小路径和」，定义写清之后，转移和初始化都是顺水推舟。- 无后效性来自「只能向右向下」：前缀怎么走不影响后续决策，这是能用状态复用取代路径枚举的根本原因。
- 只有单一来源的边界（首行首列）必须单独初始化，通用转移只对「两个来源都存在」的格子成立。
- 原地更新的合法性要能说清：遍历顺序保证读到的上方、左方都已是新值，被覆盖的旧值不再被需要。
- 面试视角：这题常被连环追问——「不许修改输入怎么办」（一维滚动数组，$O(n)$ 额外空间）；「要输出路径本身怎么办」（从终点按转移来源倒着回溯）；「格子允许四方向移动还成立吗」（不成立，会出现环，退化为最短路问题，需要 Dijkstra 一类算法）。提前把这三问想好，才算真正吃透。
易错点总结
- 错误写法：首行首列没有累加初始化，保留原值就参与转移：
grid = [[1,3,1],[1,5,1],[4,2,1]]→grid[0][2]仍是1而非前缀和5，所有依赖它的格子跟着偏小，最终结果错误地小于7。- 错误写法：对第一行第一列也套用取
min的通用转移：任意用例 → 访问grid[-1][j]或grid[i][-1]，数组越界直接崩溃。- 错误写法：初始化第一列时写成
grid[i][0] = grid[i-1][0]，忘了加自身：同一用例 → 第一列变成1, 1, 1，丢掉格子自身代价，结果偏小。- 错误写法：转移取
max而不是min：官方样例 → 算出最大路径和12而不是7。- 错误写法：每步贪心选右、下邻居中较小者：
[[1,3,1],[1,5,1],[4,2,1]]→ 走出1 → 1 → 4 → 2 → 1 = 9，错过全局最优7，局部最优不等于全局最优。- 错误写法：从右下往左上遍历却仍依赖上方左方：任意用例 → 读到的是尚未更新的原始值，转移全错。
- 错误写法：返回
grid[m][n]：任意用例 → 下标越界，正确终点是grid[m-1][n-1]。- 错误写法：改用一维滚动数组时换行不更新行首
dp[0] += grid[i][0]：多行用例 → 第一列没有累加，等价于首列初始化缺失，结果错误。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 62. 不同路径 | 中等 | 同网格模型改求路径条数，转移是求和 |
| 63. 不同路径 II | 中等 | 路径计数加障碍物，转移需分类讨论 |
| 120. 三角形最小路径和 | 中等 | 三角形结构，自底向上可省去边界特判 |
| 174. 地下城游戏 | 困难 | 必须从终点倒推，正向递推不满足无后效性 |
| 688. 骑士在棋盘上的概率 | 中等 | 状态多一维步数，转移带概率权重 |
| 931. 下降路径最小和 | 中等 | 逐行下落，三个来源取最小 |
| 1289. 下降路径最小和 II | 困难 | 禁止同列衔接，需维护每行最小与次小值 |
| 1301. 最大得分的路径数目 | 困难 | 同时维护最优值与方案数两个状态 |
| 1594. 矩阵的最大非负积 | 中等 | 乘积含负数，需同时维护最大值与最小值 |
| LCR 098. 不同路径 | 中等 | 62 题镜像，路径计数模板练习 |
| LCR 100. 三角形最小路径和 | 中等 | 120 题镜像，空间优化的对照练习 |
| 剑指 Offer 47. 礼物的最大价值 | 中等 | 同模型改求最大值，转移换成取 max
|