力扣 hot100 里的最小路径和我前后刷过三遍。第一遍照着题解抄第二遍背状态转移方程第三遍才真正想明白一件事这道题难的不是“会写动态规划”而是你能不能讲清楚为什么要用 DP、一维空间优化那行代码为什么不是随便写的。如果你是刚接触动态规划的读者或者刷过但总觉得在背题这篇就按我自己的踩坑顺序把它从暴力递归到一维优化完整拆开讲一遍。这道题本身非常标准给你一个m x n的网格每个格子有个非负整数从左上角出发每次只能向右或者向下走一步要你找一条到右下角的路径让路径上所有数字之和最小。光看题面很多人第一反应是“我每步都选值小的方向走不就行了”——这个想法错在哪后面我会单独用一组数据验证。它被收进 hot100 列表不是因为有多难而是因为它几乎把动态规划最核心的思维全部浓缩进去了状态定义、边界初始化、转移方程、空间优化一个不缺。这篇文章就沿着这条线一路拆保证你读完能自己推导而不是背题。1. 为什么这道题值得单独拆开写一次先说结论最小路径和是典型的动态规划入门题但它的价值远远不止“入门”两个字。很多题解一上来就给你dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])然后说“初始化第一行第一列完事”。这套流程背起来容易可一旦题目换成带障碍物的版本、要求输出路径、或者变成求最大路径和你就懵了。根子在于没有理解这个方程是怎么长出来的。你看题面里有两个关键约束只能向右走、只能向下走。这意味着什么意味着到达任意一个格子(i, j)的路径最后一步只可能是从左边(i, j-1)过来或者从上边(i-1, j)过来。没有第三种可能因为你现在的位置决定了你不可能从右下角绕回来。这就是动态规划里常说的“最优子结构”如果从左上角到某个格子的路径要最小那到达它前一步的那个格子也必须是“从左上角过来路径最小”的状态。你想啊假如到左边格子的路径和不是最小的那我完全可以用那条更小的路径走到左边再多走一步到当前格子总代价不就更小了吗这个逻辑本身就能自洽。还有一点容易被忽略这个问题具备“无后效性”。就是说一旦你走到了格子(i, j)之前是怎么走到这里的——走的是哪条具体路径——都不影响你接下来怎么走。下一步能去的地方只取决于当前坐标跟历史无关。这一点特别关键因为动态规划本质上就是在“剪掉历史”只保留每个状态的最优值。如果你遇到一个问题发现“我怎么来的会影响我怎么走”那说明这个状态定义不合适得换。另外暴力搜索里存在大量重复计算。简单说就是从不同的上方或左方格子走到同一个格子之后后续所有可能的路径完全一样但递归解法会把同一个格子反复求很多遍。这个特性叫“重叠子问题”正是 DP 能提速的根源。所以这道题同时包含了最优子结构、无后效性、重叠子问题三要素。把这三样在脑子里面过一遍再去看状态转移方程它就是一个顺理成章的结果不是一个需要硬记的公式。这就是我建议你认真拆解这道题的理由。2. 先走一遍暴力递归状态转移方程就不是背的了很多人学 DP 最大的误区是直接看状态转移方程。我建议反过来先写一个“最笨”的递归版本。不是说你要用它提交而是这一版能帮你把问题结构看清楚。2.1 自顶向下思考从当前位置出发的最小代价暴力递归的思路很直白定义dfs(i, j)表示从格子(i, j)走到右下角(m-1, n-1)的最小路径和。那么答案就是dfs(0, 0)。怎么算这个函数很简单你在(i, j)你可以往右走到(i, j1)也可以往下走到(i1, j)。你并不知道哪条更好所以两个方向都试一遍取代价小的那个最后再加上当前格子的值。def min_path_sum(grid): m, n len(grid), len(grid[0]) def dfs(i, j): # 已经到右下角路径代价就是当前格子的值 if i m - 1 and j n - 1: return grid[i][j] # 最后一行只能往右走 if i m - 1: return grid[i][j] dfs(i, j 1) # 最后一列只能往下走 if j n - 1: return grid[i][j] dfs(i 1, j) return grid[i][j] min(dfs(i 1, j), dfs(i, j 1)) return dfs(0, 0)这个版本逻辑上完全正确。边界条件也很直观在最后一行时没有下边可走只能一路往右在最后一列时同理。只要不在边界就朝两个方向试探。你可以把dfs想象成一个不断把问题递归分解的过程。每到一个格子你的决策空间只有两个分支整个搜索树就是一张从左上到右下的路径图。这个递归版本最大的好处是它和人类手工找路的思维方式一模一样选择太多的时候就试试完比大小。2.2 指数级成本与记忆化的自然过渡这个递归的时间复杂度是多少粗略看每个格子都会向两个方向扩展路径数量是指数级的。精确点说不同的路径条数是组合数C(mn, m)。就算网格只有 20×20路径总数也已经接近 3300 亿条跑一次你就知道什么叫绝望。但更重要的问题是为什么会有这么多重复计算举个例子你在(1, 2)这个格子上继续往后走到终点的那段路径和跟你从哪条路来到(1, 2)是无关的。可是在暴力递归里只要有一条不同的路径到达(1, 2)它就会把dfs(1, 2)重新算一遍。到达同一个格子的路径可能有很多条于是相同后缀路径被反复求了成百上千次。解决办法就是记忆化第一次算出dfs(i, j)之后把它存下来下次直接查表。from functools import lru_cache def min_path_sum_memo(grid): m, n len(grid), len(grid[0]) lru_cache(None) def dfs(i, j): if i m - 1 and j n - 1: return grid[i][j] if i m - 1: return grid[i][j] dfs(i, j 1) if j n - 1: return grid[i][j] dfs(i 1, j) return grid[i][j] min(dfs(i 1, j), dfs(i, j 1)) return dfs(0, 0)这时候递归仍然是从上往下“递”的思路但因为有缓存每个格子只会被真正计算一次时间复杂度从指数级降到了O(mn)。你会发现这不就是动态规划吗本质是一样的。只不过 DP 把“递归缓存”的顺序反过来从左上角开始自底向上填表。理解这一层你再看到状态转移方程就会觉得它是老朋友而不是从天而降的公式。3. 二维DP状态定义、初始化顺序和那个经典例子的逐格演算记忆化递归和动态规划没有本质差别只是实现方向不同。二维 DP 版本就是用一个dp数组把每个状态按依赖顺序提前算好。3.1 状态定义与边界行、列的累加逻辑定义dp[i][j]为“从左上角(0, 0)到格子(i, j)的最小路径和”。这和前面dfs的定义方向相反但结论等价。转移方程是dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])为什么依赖的是dp[i-1][j]和dp[i][j-1]因为能走到(i, j)的路径最后一步只可能来自上方或左方。我们把这两种可能里代价更小的那个状态拿过来加上当前格子的值就是到这个格子的最小代价。关键在初始化。dp[0][0]就是grid[0][0]这个没疑问。问题是第一行和第一列。第一行的格子(0, j)因为它上面没有格子只能从左边一路走过来所以dp[0][j] dp[0][j-1] grid[0][j]第一列的格子(i, 0)只能从上方一路走下来所以dp[i][0] dp[i-1][0] grid[i][0]这地方有个新手经常写错的点直接把整个dp数组初始化成grid然后只处理内部格子。表面上看没问题但如果你没把第一行第一列累加内部循环用到dp[i-1][j]或dp[i][j-1]时那还是原始网格值不是累计路径和结果全错。所以边界行、列必须单独做累加。def min_path_sum(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]如果你把grid换成[[1,3,1],[1,5,1],[4,2,1]]——这就是面试题里最常见的用例——最后答案是 7。接下来我逐格推一遍你就能看到数字是怎么流动的。3.2 逐格推演为什么结果是 7而不是 6初始化后坐标dp 值计算过程(0,0)1起点(0,1)41 3(0,2)54 1(1,0)21 1(2,0)62 4到这里第一行第一列已经成了“前缀累计”的概念。接着看内部(1,1)格子里是 5上方dp[0][1]4左方dp[1][0]2取小为 2加起来等于 7。(1,2)格子里是 1上方dp[0][2]5左方dp[1][1]7取小为 5加起来等于 6。(2,1)格子里是 2上方dp[1][1]7左方dp[2][0]6取小为 6加起来等于 8。(2,2)格子里是 1上方dp[1][2]6左方dp[2][1]8取小为 6加起来等于 7。所以答案是 7。对应路径是(0,0) → (0,1) → (0,2) → (1,2) → (2,2)也就是 1 3 1 1 1 7。这个例子很能说明问题如果你走1 → 1 → 5 → 1 → 1那条看起来更“中间”的路总和是 9反而更差。因为 DP 比较的是“累积代价”不是单步数值大小这跟人类预判路径的直觉常常不一致。3.3 循环方向的选择与复杂度分析二维 DP 的双层循环外层按行从上往下内层按列从左往右是最好理解也最常用的写法。它背后的依赖关系是计算dp[i][j]时必须已知dp[i-1][j]和dp[i][j-1]。按行从上到下时上方那个值在上一轮已经算好行内从左到右时左边那个值在当前行已经算好。所以这个顺序是“拓扑有序”的。那换成外层按列、内层按行可不可以也可以。只要保证每个状态被计算时它依赖的上方、左方状态都已经存在即可。很多时候面试官会故意顺着你的思路问“你外层为什么按行不是按列”你如果能说出“因为我当前格子只依赖上方和左方按行遍历能保证这两个依赖都已就绪”这句话比闷头写代码强很多。时间和空间复杂度都是O(mn)。这道题的网格规模通常不会太大二维数组开下来完全没问题。但既然动态规划都学了下一步自然就要问这O(mn)的空间是不是可以再压缩4. 空间优化从二维压到一维时覆盖顺序才是真正的坑空间优化这一步是面试官最爱追问的地方也是网上题解写得最粗糙的地方。很多人直接扔给你一行dp[j] grid[i][j] min(dp[j], dp[j-1])然后说“完事”。你要是没理解覆盖顺序背下来也容易写错。4.1 滚动数组的本质用“上一行的历史值”比较“当前行的新值”二维 DP 里计算第i行时其实只用到了两样东西上一行i-1的整行数据以及当前行已经算出来的左边格子。更早的行用不到了。所以我们可以用一个长度n的一维数组dp让它滚动起来。这个数组在进入第i行循环之前存的是第i-1行的结果。当它从左往右更新时dp[j]在被赋值前代表“上方格子”的路径和赋值后就变成“当前位置”的路径和而dp[j-1]已经被更新成当前行的值了正好代表“左边格子”。这个“同一格先读旧值、后写新值”的顺序就是滚动数组的精髓。如果你把内层循环改成从右往左那问题大了dp[j-1]还是上一行的旧值你会拿“上方”和“上一行的左方”去比较而不是“当前行的左方”结果完全错误。def min_path_sum(grid): m, n len(grid), len(grid[0]) # 先初始化第一行的滚动数组 dp [0] * n dp[0] grid[0][0] for j in range(1, n): dp[j] dp[j-1] grid[0][j] # 从第二行开始滚动 for i in range(1, m): dp[0] grid[i][0] # 第一列只能从上往下累积 for j in range(1, n): dp[j] grid[i][j] min(dp[j], dp[j-1]) return dp[n-1]注意dp[0] grid[i][0]这行它处理的是第一列当前dp[0]存的是上一行第一列的累计路径和加上当前行第一列的格子值正好是从起点一路走到这一列的新路径和。4.2 一维更新过程的手工推演还用grid [[1,3,1],[1,5,1],[4,2,1]]这个例子。跑一遍你就知道覆盖顺序到底是怎么起作用的。第一行初始化后dp [1, 4, 5]。进入第二行dp[0] grid[1][0]即1 1 2此时dp [2, 4, 5]。j1计算grid[1][1] min(dp[1], dp[0])也就是5 min(4, 2) 7更新dp[1]此时dp [2, 7, 5]。注意这里比较的是“上一行同列的上方值 4”和“当前行已经更新的左方值 2”刚好对应二维 DP 里的min(dp[0][1], dp[1][0])。j2计算grid[1][2] min(dp[2], dp[1])也就是1 min(5, 7) 6更新后dp [2, 7, 6]。这正好是二维版本第二行的完整结果。进入第三行同理dp[0] 4得到6。j12 min(7, 6) 8dp [6, 8, 6]。j21 min(6, 8) 7最终dp [6, 8, 7]。答案是dp[2] 7。和二维版本完全一致。如果你在纸上把这几步写一遍你会发现所谓“滚动数组”就是让同一行数组里的旧值和新值交替扮演角色。理解了这个你就不会再犯从右往左更新的错误——除非你要实现的是一维背包那种特殊场景那时才需要刻意反向遍历。4.3 写成二维还是直接写一维面试里的呈现策略我的建议是除非题目明确限制空间否则先把二维版本写出来再顺嘴提一句“这里可以用滚动数组压到 O(n)”。这不是废话而是给面试官展示你的推导能力。直接甩一维版本虽然代码简洁但有时候别人会怀疑你是不是背的你先二维再一维逻辑链条完整反而更容易得到认可。另外一个细节按列压缩也是可以的dp长度取m外层遍历列内层遍历行。但按行压缩写的人更多而且面试官一般也就默认这个写法。你只要保证自己知道为什么从左往右而不是从右往左就行别在这上面翻车。5. 原地修改、边界case以及“每步贪心”这个直觉陷阱这道题还有两个经常被忽略的点能不能直接改原数组、以及“贪心选择”为什么行不通。这两个点恰恰是面试追问的高频区。5.1 原地修改的适用边界与 integer 溢出分析如果你不想额外开数组可以直接在原grid上累加。因为grid[i][j]更新之后后续只会有右方和下方的格子用到它不会再回头读取原始值所以覆盖是安全的。def min_path_sum(grid): m, n len(grid), len(grid[0]) for i in range(m): for j in range(n): if i 0 and j 0: continue if i 0: grid[i][j] grid[i][j-1] elif j 0: grid[i][j] grid[i-1][j] else: grid[i][j] min(grid[i-1][j], grid[i][j-1]) return grid[m-1][n-1]但这里有个隐患原地修改改变了函数的入参。在竞赛平台里这没问题可如果是工程代码调用方可能还指望grid保持原样用于别处。所以我会先问一句“可以修改输入数组吗”确认之后再决定用不用原地方案。还有个衍生问题路径和会不会溢出力扣这道题的约束是网格m, n不超过 200每个格子值是非负整数。就算极端情况所有格子都是 200一条路径上的最大和也就200 * 200 * 200 8000000远在int安全范围内。但你要是把网格放大一百倍或者在面试题里被扩展成大数值场景那int就不一定稳了。用 Python 或 Go 的人不太担心这一点但用 C/Java 写的时候提一句“这里需要确认数据范围够不够”是加分行为。5.2 反直觉例子局部最优不等于全局最优回到开头说的那个陷阱很多人觉得每步选右边和下边里值更小的方向走就行这就是贪心。我举一个例子让你死心grid [ [1, 2, 1], [1, 100, 1], [3, 1, 1] ]从(0,0)出发右边是 2下边是 1贪心策略会走下边。走到(1,0)后右边是 100下边是 3贪心继续走下边。然后一路右移到终点路径是1 1 3 1 1 7。但真正的答案是多少走(0,0) → (0,1) → (0,2) → (1,2) → (2,2)总和是1 2 1 1 1 6。贪心因为第一步贪了那个“看起来小的 1”结果把自己逼进了一条后续代价很高的区域反而先横向走两步、避开 100 和大片 3整体更划算。这个例子说明路径类问题的局部最优没法拼出全局最优因为你能看到的只是当前一步而前面一小步的差异会决定后面遇到哪些格子。这也是为什么这类题不能用贪心、必须用动态规划的原因——DP 的就是“全局最小”而不是“每步最小”。5.3 如果要求输出完整路径DP要怎么改造很多面试官会在你写完最小路径和后追加一个问题“返回最小路径的坐标不止返回和。”这时候一维滚动数组就不够用了因为你要回溯每一步必须知道每个格子到底是从上方来的还是从左方来的。最简单的改造是在二维 DP 之外再开一个pre[i][j]记录来源方向。比如0表示来自上方1表示来自左方。填完 DP 表后从终点开始按照pre反向走回起点再把路径翻转过来。def min_path_sum_with_path(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] pre [[0] * n for _ in range(m)] # -1 起点, 0 上, 1 左 dp[0][0] grid[0][0] pre[0][0] -1 for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] pre[0][j] 1 for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] pre[i][0] 0 for i in range(1, m): for j in range(1, n): if dp[i-1][j] dp[i][j-1]: dp[i][j] grid[i][j] dp[i-1][j] pre[i][j] 0 else: dp[i][j] grid[i][j] dp[i][j-1] pre[i][j] 1 path [] i, j m - 1, n - 1 while True: path.append((i, j)) if pre[i][j] -1: break if pre[i][j] 0: i - 1 else: j - 1 path.reverse() return dp[m-1][n-1], path这个需求一加上空间优化就省不下来了——回溯需要全量信息一维数组存不了“每个格子的来源”。这也算是一个很好的面试互动先压空间展示能力再遇到输出路径的要求时自然过渡回二维说明你知道权衡。6. 从最小路径和出发同一DP模型在变式题里的三种变化刷题最重要的是举一反三。最小路径和不是孤立的一道题它和不同路径、不同路径 II 共享同一个骨架只是状态转移方程的内容不同。下面我把这些变化整理一下方便你横向对比。6.1 从求最小到求方案数62/63题的迁移规律力扣的不同路径题问的是从(0,0)到(m-1,n-1)有多少条不同走法。同样是只能向右向下状态定义几乎一样dp[i][j]表示从起点到(i,j)的方案数。转移方程变成了dp[i][j] dp[i-1][j] dp[i][j-1]注意区别求路径和的时候dp[i][j]是“当前格子值 两种来源路径和的最小值”求方案数时没有格子值并且要的是“两种来源的方案数之和”。初始化也不同第一行、第一列不再是累加格子值而是全部设成 1因为只有一条直线走法。到了不同路径 II带障碍物处理方式稍微复杂一点。如果grid[i][j] 1说明这里不能走直接dp[i][j] 0。真正的坑在第一行第一列的初始化如果第一行里有一个障碍那么障碍位置以及它右边的所有格子都到不了都应该设成 0不能继续赋值 1。同样的道理适用于第一列。这个细节和最小路径和的“前缀累加”有异曲同工之处都是相同方向的连锁效应。下面是三种题型的对比题目类型状态含义转移方程初始化特点最小路径和到(i,j)的最小累计代价grid[i][j] min(上方, 左方)第一行、第一列累加不同路径到(i,j)的走法数上方 左方第一行、第一列为 1带障碍不同路径到(i,j)的走法数障碍处为 0同上障碍格子跳过遇到障碍后边界行/列置 06.2 多起点、多终点、带障碍物时的初始化差异还有一种常见变形是“超级源点/超级汇点”问题起点不是(0,0)终点也不是右下角而是给定的几个点位。这时候一般做法是在 DP 前扫一遍所有可能起点或者人为加一层“虚拟行列”让初始化变统一。比如题目改成“可以从左上角区域任一边界点出发到达右下区域任一目标点”那你可以把边界上所有可能的起点都预先初始化为各自格子的值然后再进入常规 DP。本质上还是同一个模型但如果你只会死记“第一行第一列累加”这种变化就会卡住。添加障碍物时也类似如果grid[i][j]是障碍dp[i][j]要直接设成一个“无效值”。求最小值时用正无穷求方案数时用 0。这个通用技巧几乎适用所有网格 DP。6.3 个人刷题心得为什么建议用它作为DP入坑的第一道题我自己刷这道题的几次返工经历最有价值的领悟是先写暴力递归再写记忆化最后才写 DP 和空间优化。这个顺序比直接背状态转移方程慢但它把“为什么 DP 是对的”变得特别具体。后来我再遇到新的动态规划题脑子里会先浮现递归函数长什么样而不是干巴巴的方程。建议第一次接触 DP 的人这样练找几道“每个格子只依赖上方和左方”的题目最小路径和是其中最标准的代表。把它吃透接着做不同路径、带障碍版本然后把min换成max做最大路径和再想想如果允许走上下左右四方向为什么普通 DP 就不灵了——因为那时会出现环需要换成最短路算法。这一套组合拳打下来你对“状态、转移、边界”这几个词的理解会完全不一样。最后再分享一个小技巧不要只在脑子里推演拿一张纸、一个很小的网格手工画一遍滚动数组的更新过程。你花十分钟画完这张表之后遇到任何类似的空间优化题都会比别人稳很多。