很多刷题的人第一周就会撞上 LeetCode 64 这道最小路径和。题目本身短得可怜一个 m x n 的网格每个格子里放着一个非负数字从左上角出发走到右下角移动时只能向下或向右问路径上所有数字之和的最小值是多少。看起来像一道简单的迷宫题实际上它是动态规划DP入门阶段最值得反复咀嚼的题目之一。我见过不少同学上来就写 DFS跑样例能过交上去超时也见过有人记住了dp[i][j] grid[i][j] min(...)这个公式却说不清为什么面试时一追问就露馅。这篇题解不打算只给结论我会把从暴力法到二维 DP、再到滚动数组和原地修改的完整推导过程都讲清楚最后附上相关变题和面试讲题节奏。无论你是刚接触 DP还是准备跳槽复习算法这道题都值得认真走一遍。1. 题目复述与前置条件非负数字这个条件不是白给的1.1 题目在问什么输入是一个二维数组 grid行数 m列数 n每个元素是大于等于 0 的整数。要求找一条从 grid[0][0] 到 grid[m-1][n-1] 的路径路径只能向右或向下延伸使得路径经过的格子数字之和最小最后返回这个最小和。只能向右或向下意味着路径长度是固定的从左上角到右下角无论如何都必须走 m-1 次向下和 n-1 次向右总共 mn-2 步。变化的只是这 mn-2 步里哪几步向下、哪几步向右的排列顺序。这是个很重要的直觉——路径总数是有限的但数量可能爆炸下一节我会算给你看。1.2 手工走一遍标准例子官方给的标准例子是grid [[1,3,1],[1,5,1],[4,2,1]]如果暴力枚举几条典型路径对比右 → 右 → 下 → 下1 3 1 1 1 7下 → 下 → 右 → 右1 1 4 2 1 9下 → 右 → 下 → 右1 1 5 2 1 10最小的是 7所以答案就是 7。这个例子还揭示了一个常见误区很多人看到格子中间有个 5第一反应是避开 5挑小的走。但最优路径恰恰经过了左上角的那个 3因为它能让后续的整体代价变小。这说明逐格贪心在这道题上不成立全局最优不能用局部最优拼出来——这正是 DP 必须登场的原因。1.3 非负数字为什么重要题目限定数字非负主要有两个原因。第一它保证了最小路径和有直观意义也方便面试时把 dp 表的初始值设为某个较大的无穷大而不至于和真实值混淆第二如果有负数虽然转移方程在 DAG 上依然成立后面 3.4 会说明为什么但边界处理和人们的直觉解释都会变复杂。非负让这道题可以干净地聚焦到 DP 框架本身。刷题时不要忽略这类限定条件。很多题目一旦改成负数或者允许走回头路解法会完全不同允许四方向移动就变成了图上的最短路径问题需要 Dijkstra 甚至 Bellman-Ford 一类的算法。同一个 grid规则一变复杂度直接从 O(mn) 跳了一个数量级。2. 暴力法劝退用组合数学算清 DFS 的真实代价2.1 最直觉的递归写法拿到题第一反应通常是递归当前位置能往下就往下试能往右就往右试到终点统计路径和取最小。伪代码如下def dfs(grid, i, j): # 越界返回无穷大表示这条路不通 if i len(grid) or j len(grid[0]): return float(inf) # 到达右下角路径终结 if i len(grid) - 1 and j len(grid[0]) - 1: return grid[i][j] # 往下和往右两条路里选更小的 return grid[i][j] min(dfs(grid, i 1, j), dfs(grid, i, j 1))这个代码在 3x3 的例子上完全没问题毫秒级返回 7。但你把 grid 改大到 15x15 试试大概率要卡住LeetCode 的测试数据最大能到 200x200这种写法必超时。2.2 路径总数账本从 6 到 350 亿为什么递归这么慢因为从左上角到右下角的路径总数是一个组合数C((m-1)(n-1), m-1) C(mn-2, m-1)解释一下总共要走 mn-2 步其中必须包含 m-1 次向下。选择这 m-1 次向下出现在哪 m-1 个步位上剩下的 n-1 个步位自然就是向右。所以路径总数等于从 mn-2 个位置里选 m-1 个位置的组合数。几个具体数字感受一下网格规模路径总数直观感受3x3C(4,2) 6手算都行10x10C(18,9) 48620约 5 万条15x15C(28,14) 40116600约 4000 万条20x20C(38,19) ≈ 3.53e10约 353 亿条353 亿条路径每条路径要累加约 38 个数字。就算一秒能处理一亿次基本操作也需要几千秒。而且注意DFS 递归树里同一个子问题会被反复计算——比如 (i,j) 这个点从左上角可以通过好几种不同的步序到达每次到达都会重新递归一遍它后面的路径。这就是经典的重叠子问题。2.3 重叠子问题暴力与 DP 之间的那道分水岭画一张小规模的递归调用图就能看到dfs(1,1) 会被 dfs(0,1) 和 dfs(1,0) 分别调用而它们又共享了大量后续调用。这个现象叫重叠子问题overlapping subproblems。一旦意识到存在重叠子问题一个自然的改进是加缓存用一个 memo 表记录已经算过的 (i,j) 的答案下次直接取。这就是记忆化搜索也叫自顶向下的 DP。memo {} def dfs(i, j): if (i, j) in memo: return memo[(i, j)] if i len(grid) or j len(grid[0]): return float(inf) if i len(grid) - 1 and j len(grid[0]) - 1: return grid[i][j] res grid[i][j] min(dfs(i 1, j), dfs(i, j 1)) memo[(i, j)] res return res记忆化搜索的时间复杂度是 O(mn)因为每个格子最多被真正计算一次访问 memo 是常数时间。但递归本身有栈溢出风险而且用字典存 memo 的常数比较大。面试时更推荐自底向上的迭代 DP从左上角开始逐行逐列地把每个格子的最小路径和算出来后面直接用。这就是下一节的重点。3. 最后一步拆解法最小路径和的状态设计与转移方程3.1 到达 (i,j) 只有两种可能假设我们已经走到了格子 (i,j)那么路径的最后一步只可能是两种从上方 (i-1,j) 向下走一步到达从左侧 (i,j-1) 向右走一步到达。没有第三种可能因为题目不允许斜着走或回头。这个最后一步的观察是整个 DP 的起点它把从起点到终点的完整路径这个大问题拆成了从起点到某个中间点的子路径这个小一号的问题。3.2 状态定义与转移方程定义 dp[i][j] 为从 grid[0][0] 出发到达 grid[i][j] 时所有合法路径经过格子数字之和的最小值。根据上面最后一步的两种来源很容易写出转移方程dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])意思是要到 (i,j)不管是从上面下来还是从左边过来到达前一个格子时总有一个最小累计代价 dp[i-1][j] 或 dp[i][j-1]取较小者再加上当前格子自身的值 grid[i][j]就是到达 (i,j) 的最小代价。边界是起点本身dp[0][0] grid[0][0]。这一格没有前驱不需要转移。3.3 手工验证一遍状态表拿标准例子继续把 dp 表一步步填出来dp[0][0] 1dp[0][1] 1 3 4dp[0][2] 4 1 5dp[1][0] 1 1 2dp[1][1] 5 min(2, 4) 7dp[1][2] 1 min(7, 5) 6dp[2][0] 4 2 6dp[2][1] 2 min(6, 7) 8dp[2][2] 1 min(8, 6) 7最终的 dp[2][2] 7和手动枚举一致。这个过程看起来简单但请注意每一格的取值都严格只依赖它上方和左方的 dp 值这就是局部依赖的体现。3.4 无后效性为什么这里可以放心用子问题的答案后效性是指某个状态的取值会影响之后状态的求解方式。在这道题里dp[i][j] 一旦确定它只作为 dp[i1][j] 和 dp[i][j1] 的候选值参与后续计算。我们不需要知道dp[i][j] 这个最小值是通过哪条具体路径得到的只需要知道它的数值。换句话说未来怎么走只和当前累计的最小代价是多少有关和怎么走到当前这一步无关。这就是无后效性。网格图从左上到右下本身没有环所以无论数字正负这个递推都不会出现绕一圈回来更小的情况。这也是为什么即使有负数只要格子权值和移动规则不变DP 依然正确。反过来如果允许四个方向移动图里有了环DP 递推的顺序就被破坏了必须换算法。4. 初始化与边界第一行第一列是翻车高发区4.1 为什么第一行和第一列要单独处理看转移方程 dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])它对任意 i、j 都成立吗不完全成立。当 i0 时dp[i-1][j] 这一项不存在——第一行的格子只能从左边过来不可能从上方进入。同理当 j0 时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]一路向下累加很多人在这里翻车的原因是总想统一写法。如果直接用带 min 的主循环去填充第一行dp[-1][j] 会越界或者被初始化的默认 0 干扰。4.2 一个经典的错误写法假设 dp 表初始全 0然后直接从 (0,1) 开始套转移方程会得到什么dp[0][1] min(dp[-1][1], dp[0][0]) grid[0][1] min(0, 1) 3 4看起来碰巧对了dp[0][2] min(0, 4) 1 1但正确值显然是 dp[0][1] grid[0][2] 4 1 5。一旦默认值 0 参与了 min 比较结果就错了。所以要么显式处理边界要么用下面这个哨兵技巧。4.3 哨兵格技巧少写两个循环如果 dp 表比 grid 多一圈用 dp[0][1] 0 作为哨兵等价地 dp[1][0] 0 也行其余边界格子全部置为无穷大就可以让主循环统一处理所有格子。思路是给 dp 表加一圈虚拟的行和列真实起点位于 dp[1][1]它的上方和左方分别是无穷大的虚拟格和值为 0 的哨兵格min 运算不会误选无穷大。dp 尺寸为 (m1) x (n1)初始全部为很大的数令 dp[0][1] 0然后从 i1 到 m、j1 到 n 统一执行dp[i][j] grid[i-1][j-1] min(dp[i-1][j], dp[i][j-1])这个写法省了第一行、第一列两个初始化循环代价是多理解一层下标偏移。我个人的建议是平时练习用显式初始化的版本能读、能改、不容易在边界上犯迷糊面试追求代码量短时再用哨兵技巧。这两种写法都要会因为有些变体题比如三角形路径用哨兵会让主循环干净很多。4.4 极端输入别忘处理再小的输入也要考虑m1 且 n1 时直接返回 grid[0][0]m1 时只有一行答案就是第一行的累加和n1 时只有一列答案是第一列的累加和。这些情况如果你的循环从 i1、j1 开始并提前初始化了 dp[0][0]通常自然就能处理。但要先保证 grid 非空LeetCode 的测试里 grid 至少 1x1真实工程中空数组的判断不能省。5. 代码落地从二维 DP 表到简洁写法的三种实现5.1 最直白的二维 DPJava 版写 DP 题我永远建议先把最直白的版本写对再谈优化。下面是二维 DP 的 Java 实现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] grid[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; }这个版本最容易对照转移方程理解也是我在面试时最先写出来的版本。它的空间复杂度 O(mn)很多人觉得浪费但先把正确性写对、再做优化是更稳妥的策略。真实面试里从二维 DP 起步还有一个好处你能用它来验证后续滚动数组写法的正确性两个版本结果对拍一下心里踏实。5.2 Python 版原地修改直接减配def minPathSum(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) # 第一行向右累加 for j in range(1, n): grid[0][j] grid[0][j - 1] # 第一列向下累加 for i in range(1, m): grid[i][0] grid[i - 1][0] # 主循环 for i in range(1, m): for j in range(1, n): grid[i][j] min(grid[i - 1][j], grid[i][j - 1]) return grid[m - 1][n - 1]这里直接复用了 grid 数组本身作为 dp 表。每个格子只会被读取一次用于更新自己更新完之后它的原始值就不再需要所以覆盖是安全的。这种写法的额外空间复杂度是 O(1)。5.3 C 版滚动数组兼顾性能int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); vectorint 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] grid[i][j] min(dp[j], dp[j - 1]); } } return dp[n - 1]; }这个版本用长度为 n 的一维 dp 数组滚动更新。更新 dp[j] 时dp[j] 里保留的是上一行同一列的旧值相当于 dp[i-1][j]dp[j-1] 是当前行已经更新过的新值相当于 dp[i][j-1]。所以一行代码同时拿到了上方和左方的值非常巧妙。初次看可能会懵强烈建议拿 3x3 的例子在纸上模拟一遍数组变化。5.4 三种写法的取舍写法额外空间是否修改原数组推荐场景二维 DPO(mn)否教学演示、追求可读性滚动数组O(n)否面试进阶、性能敏感原地修改O(1)是允许破坏输入时需要提醒的是原地修改虽然省空间但如果后续代码还要用到原始 grid 的值就不能这么干。工程上我一般不会在真实代码里悄悄修改入参数组而是会在注释里写明副作用。面试时如果选择了原地修改一定要主动跟面试官提一句这个写法会改变输入数据展示你的工程意识。6. 复杂度这块硬骨头为什么 O(mn) 时间和 O(1) 空间是极限6.1 时间复杂度为什么不能低于 O(mn)一个基本的信息量论证输入是一个 m x n 的网格网格里每个数字都可能影响答案。哪怕只求一个粗略的下界你至少得把每个格子读一遍才知道有没有可能存在更小的值。所以任何正确算法的时间复杂度都不可能低于 O(mn)。DP 恰好达到 O(mn)在渐进意义上就是最优解。遇到面试官问还能更快吗可以从这个角度解释——不是你想不出更快的算法而是信息量决定了不可能更快。6.2 空间压缩的完整推导二维 dp 表为什么可以压缩成一维关键在依赖关系。dp[i][j] 只依赖 dp[i-1][j]上一行和 dp[i][j-1]同行的左边格。这意味着我们永远只需要上一行的完整结果和当前行左边已经算出的结果更早的行全部可以丢掉。用一维数组 dp[0..n-1] 表示当前行的累计结果外层循环 i 每推进一行dp 数组就从第 i-1 行的结果整体过渡为第 i 行的结果内层循环 j 从左到右dp[j] 在被赋值前仍然是第 i-1 行的旧值正好用作 dp[i-1][j]dp[j-1] 刚被赋值为第 i 行的新值正好用作 dp[i][j-1]。所以一行循环就能完成一行的填充且不需要任何临时变量。这个当前值既是旧值又是新值的交替使用是滚动数组的核心心法。理解它之后DP 的空间优化题基本都会做了。6.3 极端形状下的变通如果 m 和 n 差距很大比如 m10000、n2一维数组长度选 n 只要 2 个 int但如果你写的是长度 m 的版本空间会高得多。所以滚动数组有一个通用优化技巧让一维数组长度等于 min(m, n)。做法是在外层循环里遍历较长的那个维度内层遍历较短的必要时把 grid 转置一下。这个小改动能把空间压到 O(min(m,n))在很多矩阵 DP 题里都适用。6.4 空间优化的实际意义LeetCode 64 的 m、n 最大 200二维表不过 4 万个格子内存完全够用压不压缩其实无所谓。但空间优化的意义在于迁移后面你会遇到更复杂的棋盘类 DP状态可能从二维变三维比如网格加步数维度或者状态本身就要存大量信息这时候能省一行是一行会直接决定你的代码能不能跑过内存限制。所以即便这题不压缩也能过我还是建议至少把滚动数组写熟。7. 变题雷达那些长得不一样、骨子里一样的最小路径和7.1 同框架的直接变体DP 题最怕认不出来。这里列几个和最小路径和共享同一套思考框架的题目62. 不同路径同样只能向右向下问的是路径总数而不是和。转移式从 min 换成求和dp[i][j] dp[i-1][j] dp[i][j-1]初始 dp[0][0]1。63. 不同路径 II网格里加了障碍物障碍处 dp 值为 0。处理的技巧只是遇到障碍就跳过不参与递推其余框架不变。120. 三角形最小路径和树变形成三角网格每个点可以从上方、左上方来。注意三角形每一行长度不同初始化方式也跟着变。931. 下降路径最小和从顶行到底行每一步可以往左下、正下、右下走。终点格的前驱变成了三个转移式里 min 的候选从两个变成三个。题目方向限制聚合方式状态数62 不同路径右、下求和m x n63 不同路径 II右、下、障碍求和遇障碍置 0m x n64 最小路径和右、下取 minm x n120 三角形下、右下取 min三角形层数931 下降路径左下、下、右下取 minm x n这些题只要画一张小的状态图你马上能看出来它们的最后一步拆解思路完全一样差别只在前驱方向和聚合方式求和或取 min。7.2 更极端的变形反向往回推有一类问题表面完全不同但同样用 DP 的最后一步逻辑只是方向反了。比如174. 地下城游戏要从右下角往回推至少需要多少初始生命值。它的状态定义不再是从左上到当前点的最小代价而是从当前点到终点还至少需要的生命值。递推方向从右下往左上转移方程里同样是 min但语义恰好相反。这类反向题的价值在于逼你重新思考状态到底应该表示什么。最小路径和里我们问到这里的代价地下城游戏里问从这里出发的余量。状态定义不同转移方程就完全不同。这也是我特别推荐先彻底搞懂 64 题的原因——它是理解代价型 DP和余量型 DP的分水岭。7.3 用五问法快速判断一道题能不能 DP遇到新题我会按顺序问自己五个问题这是否是一个有方向、无回路的路径或序列问题到达任意位置的最后一步是否只有有限的几种来源子问题到某个中间位置的最优值是否能独立决定全局最优是否能由子问题最优组合出来是否存在重叠子问题导致暴力会重复计算若前四问答案为是、第五问明显存在基本就是 DP。这套判断法不一定覆盖所有 DP 题型但覆盖了绝大部分棋盘类和序列类题目应付面试足够了。8. 面试与刷题实战这题该怎么讲才不吃亏8.1 推荐的讲题节奏如果面试中碰到最小路径和尤其是在线做题建议按四步走先确认规则、边界和面试官明确只能向右向下以及输入规模。这一步很多人会跳过但它能避免后面沟通上的歧义。从 DFS 暴力讲起说明路径总数是指数级组合数点出重叠子问题。这能展示你的分析能力而不是只会背模板。给出二维 DP 写法完整讲清状态定义、转移方程、初始化、计算顺序四个要素。主动提出空间可以优化到 O(n) 或 O(1)解释滚动数组依赖二维 dp 表中前后行的关系说明原地修改的前提是输入可被破坏。节奏上不要一上来就甩最优解。面试官想听的是你的思考路径直接写出原地修改版反而可能让他怀疑你只会背答案尤其当你解释不清为什么能覆盖 grid 原始值的时候。8.2 高频翻车点汇总我帮人改过很多次这道题的代码以下几类错误出现频率最高忘记初始化第一行第一列直接进主循环越界读 dp[-1]或者拿默认的 0 参与 min 比较结果全错。m、n 写反把 grid[0].length 当成行数一维滚动数组越界或返回错的最后一个下标。把 min 写成 max这题要求最小值但很多人写模板写顺手了。网上能搜到不少最小路径和做法的讨论条件是 min不是 max。原地修改后忘记这是副作用提交能过但如果同一份代码里后续还想读原 grid就会被自己坑到。漏掉单行/单列场景虽然大多数实现天然覆盖但如果你用哨兵技巧还写错了哨兵位置单行数据可能直接算错。调试这些个小问题时我最常用的手段是把 3x3 或 4x4 的 dp 表格打印出来手工核对。一旦某一行对不上往回查一两个初始值基本立刻能定位。8.3 面试官可能追加的三个问题讲完基础解法面试官常会追加这三类问题提前准备一下有备无患如果 grid 里允许负数还能用这个 DP 吗可以。网格是无环 DAG只要没有回头路自左上到右下的递推顺序就能保证每个状态计算一次负数只会改变某些中间结果不会破坏依赖关系。如果允许四方向移动呢不行。网格里出现了环DP 的拓扑序失效退化为带权图最短路径问题。非负权用 Dijkstra含负权要用 Bellman-Ford 或 SPFA。如果我不想修改入参数组又想要 O(1) 空间呢做不到除非允许破坏输入。这是信息存储的下界不额外开数组又不动原数组就没有地方保存中间状态。这类追问的本质是在考你对 DP 适用边界的理解。把 3.4 的无后效性和环的关系想清楚回答起来就很有底气。8.4 一个值得记住的思考习惯最后分享一个我体会很深的习惯做棋盘类 DP先不要急着写代码拿一支笔在纸上把网格画出来然后从终点往回走一步、再走一步亲手标出每个格子的依赖来源。绝大多数 DP 题的问题都出在状态定义和依赖来源没想清楚就动手。网格题尤其如此因为你能把所有依赖关系用图形画出来这在其他类型题目里没那么直观。这道最小路径和是我用来带朋友入门这个习惯的第一题。画完一遍 dp 表你会在很多看似不同的题目里反复看到同一张表——那时候DP 的大门就算真正打开了。