题目描述
思路解析
一句话答案：LeetCode 64 最小路径和的标准解法是二维动态规划：dp[i][j] 表示从左上角走到 (i,j) 的最小路径和，由于每格只能从上方或左方来，转移是本格数字加 min(dp[i-1][j], dp[i][j-1])。首行首列只有单一来路，先单向累加打底，右下角一格就是答案，时间 O(m×n)、空间可压到 O(n)。
最小路径和这道题在问什么
一个 m×n 的网格，每格有一个非负数字。从左上角 (0,0) 出发，每步只能向右或向下走一格，到达右下角 (m-1,n-1)，求沿途数字之和最小是多少。两个隐含条件值得先记下：只能右、下两个方向，意味着路径不会走回头路；格子里的数非负，意味着不存在「绕远反而更省」的怪路。
为什么不能枚举所有路径
暴力思路是回溯出每一条从左上到右下的路径、逐条算和取最小。但路径条数是组合级的：每条路要走 m-1 步向下、n-1 步向右，排列方式随网格增大爆炸式增长，稍大的网格就算不完。
浪费在哪里？海量路径共享着相同的前半段。其实走到任何一个格子 (i,j) 时，前面那段路怎么绕的根本不重要，对后续决策有用的信息只有一个数：到这里的最小花费。把每个格子的这个数记下来复用，指数条路径就坍缩成 m×n 个子问题——这就是无后效性的白话版：到达 (i,j) 之后怎么走，与之前的路线无关。
dp 转移方程为什么是 min 加本格
定义 dp[i][j] 为从起点走到 (i,j) 的最小路径和。任何到达 (i,j) 的路，最后一步只有两种可能：从上方 (i-1,j) 下来，或从左方 (i,j-1) 过来。走上方来路的最优花费是 dp[i-1][j]，走左方来路的最优是 dp[i][j-1]，二者取小、再加上本格数字，就是 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。
为什么这样就是对的？假如最优路径经由上方进入 (i,j)，它在 (i-1,j) 之前的部分必然也是到 (i-1,j) 的最优——否则把那段换成更省的，总和还能更小，与最优矛盾。所以只需比较两条来路各自的最优值。注意是取 min 不是相加：一条路只能从一个方向进来，把两个来路加在一起没有物理意义，这是初学者最常写错的一笔。
首行和首列为什么要单独处理
第一行的格子上方没有邻居，只能从左边一路走过来，所以是前缀累加：dp[0][j] = dp[0][j-1] + grid[0][j]；第一列同理只能从上面来。如果不单独处理、对不存在的方向也去取 min，要么数组越界，要么取到未初始化的 0 而把答案算小。起点 dp[0][0] 就是 grid[0][0] 本身。打好这一行一列的底，内部格子逐行推过去，右下角 dp[m-1][n-1] 即答案——对示例那个 4×5 网格，结果是 22。
复杂度多少，空间还能怎么省
每个格子恰好算一次、每次 O(1)，时间 O(m×n)；存整张表空间 O(m×n)。因为 dp[i][j] 只依赖上一行同列和本行左邻，可以用一维数组滚动：dp[j] = grid[i][j] + min(dp[j], dp[j-1])，其中 dp[j] 更新前恰好是上一行的值、dp[j-1] 是本行刚算完的左邻，空间降到 O(n)。若题目允许改输入，甚至能直接在 grid 上原地累加做到 O(1) 额外空间。最后提醒：答案在右下角那格，别返回错位置。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句「本格值 + 上、左较小的」，下面每一格都在套它。
起点 (0,0)：还没走任何一步，路径和就是这格自己的数字，dp[0][0] = 3。
第一行 (0,1)：上面没有格子，只能从左边那格走过来，左边和 3 加本格 1 = 4。
第一行 (0,2)：上面没有格子，只能从左边那格走过来，左边和 4 加本格 5 = 9。
第一行 (0,3)：上面没有格子，只能从左边那格走过来，左边和 9 加本格 2 = 11。
第一行 (0,4)：上面没有格子，只能从左边那格走过来，左边和 11 加本格 4 = 15。
第一列 (1,0)：左边没有格子，只能从上面那格走过来，上面和 3 加本格 2 = 5。
算 (1,1)：正上方 dp[0][1]=4（蓝），正左方 dp[1][0]=5（蓝），先挑两条来路里较小的 4。
较小的是 4（走上面更省），再加本格 8 = 12，填进 (1,1)。
算 (1,2)：正上方 dp[0][2]=9（蓝），正左方 dp[1][1]=12（蓝），先挑两条来路里较小的 9。
较小的是 9（走上面更省），再加本格 3 = 12，填进 (1,2)。
算 (1,3)：正上方 dp[0][3]=11（蓝），正左方 dp[1][2]=12（蓝），先挑两条来路里较小的 11。
较小的是 11（走上面更省），再加本格 6 = 17，填进 (1,3)。
算 (1,4)：正上方 dp[0][4]=15（蓝），正左方 dp[1][3]=17（蓝），先挑两条来路里较小的 15。
较小的是 15（走上面更省），再加本格 1 = 16，填进 (1,4)。
第一列 (2,0)：左边没有格子，只能从上面那格走过来，上面和 5 加本格 4 = 9。
算 (2,1)：正上方 dp[1][1]=12（蓝），正左方 dp[2][0]=9（蓝），先挑两条来路里较小的 9。
较小的是 9（走左边更省），再加本格 2 = 11，填进 (2,1)。
算 (2,2)：正上方 dp[1][2]=12（蓝），正左方 dp[2][1]=11（蓝），先挑两条来路里较小的 11。
较小的是 11（走左边更省），再加本格 7 = 18，填进 (2,2)。
算 (2,3)：正上方 dp[1][3]=17（蓝），正左方 dp[2][2]=18（蓝），先挑两条来路里较小的 17。
较小的是 17（走上面更省），再加本格 1 = 18，填进 (2,3)。
算 (2,4)：正上方 dp[1][4]=16（蓝），正左方 dp[2][3]=18（蓝），先挑两条来路里较小的 16。
较小的是 16（走上面更省），再加本格 5 = 21，填进 (2,4)。
第一列 (3,0)：左边没有格子，只能从上面那格走过来，上面和 9 加本格 6 = 15。
算 (3,1)：正上方 dp[2][1]=11（蓝），正左方 dp[3][0]=15（蓝），先挑两条来路里较小的 11。
较小的是 11（走上面更省），再加本格 3 = 14，填进 (3,1)。
算 (3,2)：正上方 dp[2][2]=18（蓝），正左方 dp[3][1]=14（蓝），先挑两条来路里较小的 14。
较小的是 14（走左边更省），再加本格 2 = 16，填进 (3,2)。
算 (3,3)：正上方 dp[2][3]=18（蓝），正左方 dp[3][2]=16（蓝），先挑两条来路里较小的 16。
较小的是 16（走左边更省），再加本格 4 = 20，填进 (3,3)。
算 (3,4)：正上方 dp[2][4]=21（蓝），正左方 dp[3][3]=20（蓝），先挑两条来路里较小的 20。
较小的是 20（走左边更省），再加本格 2 = 22，填进 (3,4)。
表填满了。右下角 dp[3][4] = 22，就是从左上走到右下、数字之和最小的那条路。
极端输入正好被「首行只加左、首列只加上」覆盖。
两个高频追问。
参考代码
def minPathSum(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] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]复杂度
- 时间：O(m×n)，每格只算一次
- 空间：O(m×n)，存了整张表（可压成一行 O(n)）
易错点
面试追问把动画讲成自己的话
追问只问最小和，能优化到 O(n) 空间吗？
追问如果还要还原出具体走的那条路径呢？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
不同路径 II
LeetCode 63 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题