题目描述
给定一个包含非负整数的 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
提示：
-
1 <= m, n <= 200
-
0 <= grid[i][j] <= 200
解题思路
这题本质是 动态规划（DP）：
定义状态：
dp[i][j] = 到达 (i,j) 的最小路径和
状态转移：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
-
从上方 (dp[i-1][j]) 或左方 (dp[i][j-1]) 到达
边界条件：
-
起点 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 代码
int minPathSum(int** grid, int gridSize, int* gridColSize) {
int m = gridSize;
int n = gridColSize[0];
int dp[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] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
一维 DP 优化（空间优化）
-
由于每次只需要上一行的数据，可以滚动数组，空间从 O(m*n) 优化到 O(n)
int minPathSum(int** grid, int gridSize, int* gridColSize) {
int m = gridSize;
int n = gridColSize[0];
int dp[n];
dp[0] = grid[0][0];
// 第一行
for (int j = 1; j < n; j++)
dp[j] = dp[j-1] + grid[0][j];
for (int i = 1; i < m; i++) {
dp[0] += grid[i][0]; // 第一列
for (int j = 1; j < n; j++) {
dp[j] = (dp[j] < dp[j-1] ? dp[j] : dp[j-1]) + grid[i][j];
}
}
return dp[n-1];
}
复杂度分析
| 二维 DP | O(m*n) | O(m*n) |
| 一维 DP | O(m*n) | O(n) |
拓展思考
路径打印：如果想输出最小路径，可以使用额外的 parent 数组记录路径。
多源最短路径：这题是二维网格上经典的 动态规划最短路径问题，类似于 BFS 最短路径问题，但有 DP 优化。
面试小技巧：
-
先写二维 DP，保证正确
-
再考虑滚动数组优化空间
-
注意边界处理：第一行、第一列
✅ 总结：
LeetCode 64 题是典型的 DP 网格问题，核心思想是 每一步取左和上最小值，结合边界初始化即可求解。空间优化可以用滚动数组，将空间复杂度降为 O(n)。
