最小路径和
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1
示例 2
模拟答题者思考
1. 最直接：DFS/BFS 枚举所有「只向右或向下」的路径，每条路径累加格子数字求和，取最小——正确但指数级，m,n 可达 200 会超时。
2. 重复在哪里？到达 (i,j) 的最优路径，最后一步要么从 (i-1,j) 来，要么从 (i,j-1) 来——与 #62、#63 相同的网格 DP 结构，但子问题从「计数」变成「求最小和」。
3. 子问题定义：设 dp[i][j] = 到 (i,j) 的最小路径和。则 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。边界：第一行只能从左边来，第一列只能从上边来。
4. 手推示例 1：dp[2][2]=grid[2][2]+min(dp[1][2],dp[2][1])=1+min(7,7)=7，与输出一致。
5. 可原地修改 grid 当 DP 表（题目允许修改输入时），或保留一维滚动数组将空间压到 O(n)。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dp[i][j] | int[][] | 定义：从左上角 (0,0) 走到 (i,j) 且路径数字总和的最小值维护： dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])（第一行/列只有单一来源）更新：按行优先双重循环， i 从 0 到 m-1、j 从 0 到 n-1 递增填表 |
grid[i][j] | int | 定义：格子代价，路径经过该格时必须累加此值 维护：只读输入，作为递推的「当前步花费」 更新：每次计算 dp[i][j] 时加上 grid[i][j] |
dp[0][*] / dp[*][0] | int | 定义：第一行、第一列格子的最小路径和边界 维护：从起点只能一直向右或向下延伸，无分支可选 更新： dp[0][0]=grid[0][0]；dp[0][j]=dp[0][j-1]+grid[0][j]；dp[i][0]=dp[i-1][0]+grid[i][0] |
dp[j]（滚动） | int[] | 定义：空间优化时的一维数组，dp[j] 表示当前行第 j 列的最小路径和维护：遍历每行时， dp[j] 先代表「来自上方」的值，再与左方取 min 并加当前格代价更新： dp[j] = grid[i][j] + (j>0 ? min(dp[j], dp[j-1]) : dp[j]) |
落码步骤
1. 取 m, n；可直接在 grid 上原地 DP，或新建 dp[n] 滚动数组
2. 初始化第一行：从左到右累加 grid[0][j] += grid[0][j-1]
3. 从第 2 行起遍历 i：先处理第一列 grid[i][0] += grid[i-1][0]
4. 内层 j 从 1 到 n-1：grid[i][j] += min(grid[i-1][j], grid[i][j-1])
5. 返回 grid[m-1][n-1]（或滚动数组的 dp[n-1]）
代码实现
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for j in range(1, n):
grid[0][j] += grid[0][j - 1]
for i in range(1, m):
grid[i][0] += grid[i - 1][0]
for j in range(1, n):
grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
return grid[m - 1][n - 1]class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int j = 1; j < n; j++)
grid[0][j] += grid[0][j - 1];
for (int i = 1; i < m; i++) {
grid[i][0] += grid[i - 1][0];
for (int j = 1; j < n; j++)
grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
}
return grid[m - 1][n - 1];
}
};
// 时间 O(mn)，空间 O(1)（原地修改 grid）复杂度分析
O(m × n)
O(n)（滚动数组）
常见坑
边界行/列未单独处理：第一行只能从左累加、第一列只能从上累加，不能直接套 min(上,左)，否则 dp[0][0] 会被错误地加两次。
与 #62 混淆用加法计数：本题是「最小和」，递推是 grid[i][j] + min(...)，不是路径条数相加。
滚动数组方向搞反：按行滚动时 dp[j] 更新前保存的是「上方」，更新后与 dp[j-1]（左方）取 min，顺序不能颠倒。
必测边界 Case
[[5]] → 5（起点即终点，无移动）
[[1,2,3]] → 6（只能一直向右）
[[1],[2],[3]] → 6（只能一直向下）
[[0,0],[0,0]] → 0（任意路径和均为 0）
[[200,200],[200,200]] → 800（验证 int 范围内不溢出，本题代价 ≤200、路径 ≤400 格）