题目描述
思路解析动画文字版
示例网格 · 先认路：左上角是起点、右下角是终点。每一步只能向右或向下走，所以一定是从左上往右下、单向推进，不会回头。
最直接的想法是把所有「右、下」走法都列出来，各算一次总代价，再取最小。可路径条数随网格指数增长，而且很多路的前半段是重叠的，被一遍遍重复求和，太慢。
为什么贪心会翻车 · 真跑一遍：有人想「每步就挑右、下里小的那格」。从 1 出发：右是 3、下是 1，挑下；到下一格右是 5、下是 4，挑下；再一路向右。这条贪心路 1+1+4+2+1 等于 9。可正解是 7。贪心只看眼前一步，省了开头却被结尾的大格坑了。所以必须用 DP 通盘考虑。
转折：用 dp[i][j] 记「走到 第 i 行第 j 列 的最小代价」，每格只算一次。一个格子只能从上面或左边来，那当然挑代价小的那条接上。第一行、第一列只有一条路，前缀累加即可。
建表 · 起点：建一张 3 乘 3 的 dp 表。起点 dp[0][0] 没有别处可来，就等于它自己的代价 1。其余先空着。
第一行 · 只能向右累加：第一行头顶没格子，只能一路向右，所以是前缀和：1、然后 1+3 等于 4、再 4+1 等于 5。这一行不用取较小（没有别的路可选）。
第一列 · 只能向下累加：第一列左边没格子，只能一路向下：1、然后 1+1 等于 2、再 2+4 等于 6。边界铺好了，下面开始对内部格子取较小。
填 (1,1) · 取较小的那条：第 1 行第 1 列这格代价是 5，可从上面（dp 等于 4）或左边（dp 等于 2）来。取较小，挑左边的 2，把上面那条 4 丢掉——这就是核心的「取小、弃大」分支。dp 等于 2+5 等于 7。
填 (1,2) · 这次上比左小：这格代价是 1，从上面（dp 等于 5）或左边（dp 等于 7）来。这回反过来——上面 5 更小，丢掉左边的 7。dp 等于 5+1 等于 6。可见每格选哪条全看谁小，不固定。
填 (2,1) · 取左：这格代价是 2，从上面（dp 等于 7）或左边（dp 等于 6）来，取较小挑左边 6，丢掉上面 7。dp 等于 6+2 等于 8。
右下角 · 取上：终点这格代价是 1，从上面（dp 等于 6）或左边（dp 等于 8）来，取较小挑上面 6。dp 等于 6+1 等于 7，正是那条 1 到 3 到 1 到 1 到 1 的最小路径和。
灵魂帧慢放 · 一格三态：把任意一格的填法放慢看：先点亮它依赖的两格——正上方和正左方；在这两个 dp 值里取较小；最后加上自己这格的代价，写进去落定。每一格都是这「看两格、取小、加自己」三步，全表重复这个动作而已。
答案：右下角 dp[2][2] 等于 7 就是答案。整张表每格都在「上、左」里挑了代价更小的一条接上来。
同一张网格 DP 表，换聚合方式就解不同题：计数用加法（不同路径），求最小用 min（本题），求最大用 max。骨架一样，只改那一个聚合符。
面试追问：贪心为何错、空间怎么压、怎么还原路径、为何依赖单向——这四问把本题讲透。
迁移阶梯：把这题练到能复述后，去同类题迁移：不同路径（把 min 换成加法求计数）、三角形最小路径和、下降路径最小和——都是这张表换个聚合符或换个来源方向。卡住可问 AI 助教或进通关训练逐题打。
边界三连：1 乘 1 时答案就是那一格；单行、单列时只剩前缀累加这一条边界逻辑，内部双重循环根本进不去，刚好被边界处理覆盖。
参考代码
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]复杂度
- 时间复杂度：O(m × n)，每个格子只做一次 min 和一次加法，共 m×n 格
- 空间复杂度：O(m × n)，一张 m×n 的 dp 表；因每格只依赖上、左，可压成一行 O(n)
可套用的代码模板
记四步判据：状态定义、边界前缀累加、内部聚合加当前格、答案取右下角。把 AGG 换成 min 就是本题，换 max 求最大路径和，换加法就是「不同路径」计数。
# 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=路径计数易错点
面试追问把动画讲成自己的话
追问为什么贪心「每步挑右、下里小的」不对？
追问空间能从 O(m×n) 压到多少？怎么压？
追问如果要的是「最小路径本身」而不只是和，怎么办？
追问如果允许向上、向左走（四方向）还能用这个 DP 吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
不同路径 II
LeetCode 63 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题