LeetCode 64中等二维 DP
最小路径和 图解题解
这道题到底在问什么
网格每格是非负代价，每步只能向右或向下，求从左上角到右下角路径上代价之和的最小值。
- 网格
- 1 3 1 / 1 5 1 / 4 2 1
- 输出
- 7
最优解：一步一步想明白
- 3只能向右或向下左上角是起点、右下角是终点。每一步只能向右或向下走，所以一定是从左上往右下、单向推进，不会回头。
- 4最直接的想法是把所有「右、下」走法都列出来，各算一次总代价，再取最小。可路径条数随网格指数增长，而且很多路的前半段是重叠的，被一遍遍重复求和，太慢。
- 5每步只挑小的：得 9，错！有人想「每步就挑右、下里小的那格」。从 1 出发：右是 3、下是 1，挑下；到下一格右是 5、下是 4，挑下；再一路向右。这条贪心路 1+1+4+2+1 等于 9。可正解是 7。贪心只看眼前一步，省了开头却被结尾的大格坑了。所以必须用 DP 通盘考虑。
- 6转折：用 dp[i][j] 记「走到 第 i 行第 j 列 的最小代价」，每格只算一次。一个格子只能从上面或左边来，那当然挑代价小的那条接上。第一行、第一列只有一条路，前缀累加即可。
- 7dp[0][0] = grid[0][0] = 1建一张 3 乘 3 的 dp 表。起点 dp[0][0] 没有别处可来，就等于它自己的代价 1。其余先空着。
- 8dp 第一行 = 1, 4, 5第一行头顶没格子，只能一路向右，所以是前缀和：1、然后 1+3 等于 4、再 4+1 等于 5。这一行不用取较小（没有别的路可选）。
- 9dp 第一列 = 1, 2, 6第一列左边没格子，只能一路向下：1、然后 1+1 等于 2、再 2+4 等于 6。边界铺好了，下面开始对内部格子取较小。
- 10min(上4, 左2) + 5 = 7第 1 行第 1 列这格代价是 5，可从上面（dp 等于 4）或左边（dp 等于 2）来。取较小，挑左边的 2，把上面那条 4 丢掉——这就是核心的「取小、弃大」分支。dp 等于 2+5 等于 7。
- 11min(上5, 左7) + 1 = 6这格代价是 1，从上面（dp 等于 5）或左边（dp 等于 7）来。这回反过来——上面 5 更小，丢掉左边的 7。dp 等于 5+1 等于 6。可见每格选哪条全看谁小，不固定。
- 12min(上7, 左6) + 2 = 8这格代价是 2，从上面（dp 等于 7）或左边（dp 等于 6）来，取较小挑左边 6，丢掉上面 7。dp 等于 6+2 等于 8。
- 13min(上6, 左8) + 1 = 7终点这格代价是 1，从上面（dp 等于 6）或左边（dp 等于 8）来，取较小挑上面 6。dp 等于 6+1 等于 7，正是那条 1 到 3 到 1 到 1 到 1 的最小路径和。
- 14依赖(蓝) → 取较小 → 落定(绿)把任意一格的填法放慢看：先点亮它依赖的两格——正上方和正左方；在这两个 dp 值里取较小；最后加上自己这格的代价，写进去落定。每一格都是这「看两格、取小、加自己」三步，全表重复这个动作而已。
- 15dp[2][2] = 7右下角 dp[2][2] 等于 7 就是答案。整张表每格都在「上、左」里挑了代价更小的一条接上来。
- 18同一张网格 DP 表，换聚合方式就解不同题：计数用加法（不同路径），求最小用 min（本题），求最大用 max。骨架一样，只改那一个聚合符。
- 23把这题练到能复述后，去同类题迁移：不同路径（把 min 换成加法求计数）、三角形最小路径和、下降路径最小和——都是这张表换个聚合符或换个来源方向。卡住可问 AI 助教或进通关训练逐题打。
⚠️ 容易写错的地方
✗ 错：第一行、第一列也套 min(上, 左) 公式
✓ 对：第一行、第一列单独前缀累加
第一行没有「上」、第一列没有「左」，硬套 min 会读到还没填、值为 0 的不存在格，把最小值错误地压成 0
✗ 错：取完 min(上, 左) 就忘了 + grid[i][j]
✓ 对：min(上, 左) 之后必须再加当前格代价
路径和要算上当前格自己的代价，漏加会少算整整一格
✗ 错：用贪心「每步挑小的」代替 DP
✓ 对：老老实实填整张 dp 表
贪心只看眼前一步，可能为了省开头一格而走进结尾的大代价区，得不到全局最优（本题示例贪心得 9、正解 7）
完整代码（Python / C++ / Java）
Python
class Solution:
def minPathSum(self, grid):
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j] # 第一行
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0] # 第一列
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]C++
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
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] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
return dp[m-1][n-1];
}
};Java
class Solution {
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];
}
}套路模板 · 网格DP 挖空骨架（背判据）
# 1) 状态：dp[i][j] = 走到 (i,j) 的【最优值】
dp[0][0] = grid[0][0]
# 2) 边界：第一行只来自左，第一列只来自上 —— 单独前缀累加
for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]
# 3) 转移：内部格从【上 dp[i-1][j]】【左 dp[i][j-1]】聚合 + 当前格
for i in range(1, m):
for j in range(1, n):
dp[i][j] = AGG(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1] # 4) 答案在右下角
# AGG 换 min=最小和 / max=最大和 / a+b=路径计数// 1) dp[i][j] = 走到 (i,j) 的最优值
dp[0][0] = grid[0][0];
// 2) 边界：第一行只来自左、第一列只来自上
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];
// 3) 转移：AGG = min / max / 加法 据题替换
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = AGG(dp[i-1][j], dp[i][j-1]) + grid[i][j];
return dp[m-1][n-1]; // 4) 答案在右下角// 1) dp[i][j] = 走到 (i,j) 的最优值
dp[0][0] = grid[0][0];
// 2) 边界：第一行只来自左、第一列只来自上
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];
// 3) 转移：AGG = Math.min / Math.max / 加法 据题替换
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = AGG(dp[i-1][j], dp[i][j-1]) + grid[i][j];
return dp[m-1][n-1]; // 4) 答案在右下角复杂度
时间复杂度
O(m × n)
每个格子只做一次 min 和一次加法，共 m×n 格
空间复杂度
O(m × n)
一张 m×n 的 dp 表；因每格只依赖上、左，可压成一行 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最小路径和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么贪心「每步挑右、下里小的」不对？+
贪心只看当前一步，可能为省开头一格而被结尾的大代价坑了。本题示例贪心走出 1+1+4+2+1 等于 9，而最优是 7。必须用 DP 把每格的全局最小都记下来。
空间能从 O(m×n) 压到多少？怎么压？+
能压到 O(n)。因为算第 i 行只用到第 i-1 行，用一维 dp，遍历到列 j 时 dp[j] 还是上一行的值（即「上」）、dp[j-1] 是本行刚算的（即「左」），原地更新 dp[j]=min(dp[j],dp[j-1])+grid[i][j] 即可。
如果要的是「最小路径本身」而不只是和，怎么办？+
额外记一个 from[i][j] 标记这格是从上还是从左转移来的；填完表后从右下角沿 from 反向回溯到左上，倒序就是最优路径。
如果允许向上、向左走（四方向）还能用这个 DP 吗？+
不能。本题 DP 成立的前提是「只能右、下」，保证依赖的上、左两格在当前格之前就算好、无环。四方向会出现互相依赖的环，要改用 Dijkstra 这类最短路算法。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。