刷题刷到 LeetCode 64“最小路径和”的朋友多半已经在动态规划门口徘徊了一阵子。这道题在面试和笔试里出现频率很高解法里浓缩了 DP 最核心的几个动作——状态定义、转移方程、边界初始化、空间优化每一步都能展开讲不少东西。它解决的是这样一个问题给定一个 m×n 网格每个格子上有非负整数从左上角走到右下角每次只能向右或向下走一步问路径上数字之和最小是多少。适合刚接触 DP、想通过一道经典题建立完整解题框架的人也适合刷题一阵子但在滚动数组优化上老是绕晕的老手。我先说结论这题的标准解法是动态规划二维版本空间复杂度 O(mn)优化后可以压到 O(n)甚至原地修改数组做到 O(1)。整道题的思维链条不算长但每一环都有讲究下面按我的理解逐层拆开讲。1. 题目到底在问什么先看明白再动手1.1 路径不是随便走的很多人拿到这道题第一反应是“不就是找一条路吗DFS 走一遍不就行了”。先看题目约束每次只能向右或者向下移动一步。这个约束决定了路径是有方向的、单调的——你永远不会往回走所以从左上角到右下角一共要走 mn-2 步其中向下 m-1 步、向右 n-1 步组合关系是固定的。这一点极其重要。如果题目改成“可以上下左右任意走”那这道题的性质就完全变了变成带环图上的最短路径问题得用 Dijkstra 或者 A*而不再是我们今天讨论的 DP。很多人忽略了“方向受限”这个前提以至于后面理解状态转移时总觉得哪里不对劲。1.2 暴力搜索为什么撑不住先算一笔账。m×n 网格中所有不同路径的数量等于组合数 C(mn-2, m-1)。一个 10×10 的网格路径数是 C(18,9)48620看起来还能接受但网格稍微大一点比如 20×20路径数是 C(38,19)超过 350 亿。就算你的电脑每秒能检查一亿条路径也要跑几分钟才能枚举完 20×20 的情况而 LeetCode 的测试用例可以到 200×200DFS 直接超时到怀疑人生。组合数爆炸的本质是路径之间存在大量重叠的子问题。你从 (0,0) 出发可能有很多条不同的路线最终都走到同一个格子 (i,j)而从 (i,j) 到终点的后续路径又是一样的重复计算了一万遍。这种“子问题重叠”正是动态规划发挥优势的地方——记住每个格子的答案避免重复劳动。2. 动态规划解法状态设计与转移方程推导2.1 状态定义dp[i][j] 表示什么定义一个二维数组 dp[i][j]表示从左上角 (0,0) 出发到达格子 (i,j) 的最小路径和。这个定义非常自然反正路径只能向右向下走要到达 (i,j)上一步只可能是从 (i-1,j) 向下走或者从 (i,j-1) 向右走。换句话说到达 (i,j) 的最小代价一定来自这两个相邻格子中较小的那个最小路径和再加上当前格子本身的数字。所以转移方程可以写为dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])这里有两个值得琢磨的点。第一为什么要用 min 而不是别的因为题目要求最小路径和我们要走的每一步都选择代价更小的来路。第二为什么只需要知道 dp[i-1][j] 和 dp[i][j-1] 就够了因为在“只能向右向下”的规则下所有能到达 (i,j) 的路径都必须经过这两个邻居之一而这两个邻居的最优值已经被算出来了这就是最优子结构。2.2 边界初始化是第一道坎转移方程不是万能的它有一个前提i 和 j 都不能是 0。当 i0 时格子在第一行它的上方没有任何格子“从上方过来”这条路不存在当 j0 时格子在第一列左边没有格子。这些边界必须单独处理。第一行的初始化逻辑是从 (0,0) 走到 (0,j)只能一路向右走没有别的选择所以 dp[0][j] dp[0][j-1] grid[0][j]。同理第一列只能一路向下走所以 dp[i][0] dp[i-1][0] grid[i][0]。起点 dp[0][0] 就是 grid[0][0]。这个初始化动作经常被忽略。如果直接套用转移方程第一行会试图访问 dp[-1][j]第一列会访问 dp[i][-1]要么越界要么结果完全错误。类似地如果你选择在循环里加 if 判断边界情况也要保证逻辑正确。2.3 手推一个 3×3 的例子光看公式容易飘找个具体的网格亲手填一遍表。就用 LeetCode 官方示例| 1 | 3 | 1 | | 1 | 5 | 1 | | 4 | 2 | 1 |按照规则dp 表会这样填充。先初始化第一行dp[0][0]1dp[0][1]134dp[0][2]415。再初始化第一列dp[1][0]112dp[2][0]246。接着从 (1,1) 开始计算dp[1][1] 5 min(dp[0][1]4, dp[1][0]2) 52 7dp[1][2] 1 min(dp[0][2]5, dp[1][1]7) 15 6dp[2][1] 2 min(dp[1][1]7, dp[2][0]6) 26 8dp[2][2] 1 min(dp[1][2]6, dp[2][1]8) 16 7最终答案是 dp[2][2]7。手推一遍你就能感觉到dp 表是一个从左上角往右下角“扩散”的过程每个格子都稳稳站在前人的肩膀上。2.4 二维 DP 的代码参考public int minPathSum(int[][] grid) { int m grid.length; int 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]; }Python 写法类似把 Math.min 换成 min 即可。这个版本的时间复杂度 O(mn)空间复杂度 O(mn)。作为一道题目的“正确解”到这一步已经能 AC 了。3. 空间优化从二维表到滚动数组3.1 为什么可以压缩到一维观察转移方程dp[i][j] 只依赖 dp[i-1][j]上一行和 dp[i][j-1]当前行左边再往前的数据完全没有用到。也就是说整个二维表中那些“上上行”的旧值一旦被当前行用完之后就失去价值了。那我们完全可以用一个长度为 n 的一维数组滚动地存放“上一行”的结果边遍历边更新成“当前行”的结果。这有点像做连续求和你不需要记住每天的数值存一个数组只需要一个变量不断累加即可。滚动数组就是同样的思想只保留运算必需的最近状态。3.2 更新顺序是滚动数组的灵魂用一维数组 dp[j] 时逻辑会发生微妙的变化。遍历到第 i 行时dp[j] 在更新前存的还是上一行第 j 列的结果正好代表 dp[i-1][j]dp[j-1] 在本次循环里已经被更新过了它现在代表 dp[i][j-1]所以新值 grid[i][j] min(旧 dp[j], 新 dp[j-1])。这里的关键是j 必须从 0 到 n-1 正向遍历。如果反过来从右往左更新dp[j-1] 还是上一行的旧值左边的信息就丢了整个结果会错得离谱。我第一次写滚动数组就栽在方向上调了半天才发现。3.3 一维滚动数组代码参考public int minPathSum(int[][] grid) { int m grid.length; int n grid[0].length; int[] dp new int[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] dp[0] grid[i][0]; for (int j 1; j n; j) { dp[j] grid[i][j] Math.min(dp[j], dp[j - 1]); } } return dp[n - 1]; }特别注意第二层循环里 dp[0] 的更新因为第一列没有左边的格子它只能继承上一行同列的值也就是 dp[0] grid[i][0]。这一步漏掉的话第一列的答案全错。Python 版本def minPathSum(self, 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[-1]空间复杂度从 O(mn) 降到 O(n)。如果网格是 m 远小于 n 的情况还可以把数组长度定为 min(m,n)外层循环较大的维度理论可以继续优化一点但实际写起来要格外小心一般面试不要求。3.4 还能不能再省原地修改 grid如果面试官追问“能不能 O(1) 空间”还有一个方案直接在原数组 grid 上做累加把 grid 本身当成 dp 表。因为每个格子只需要读取原值一次更新之后它就变成 dp 值继续供右侧和下方使用。写法如下public int minPathSum(int[][] grid) { int m grid.length; int n grid[0].length; for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0 j 0) continue; int up i 0 ? grid[i - 1][j] : Integer.MAX_VALUE; int left j 0 ? grid[i][j - 1] : Integer.MAX_VALUE; grid[i][j] Math.min(up, left); } } return grid[m - 1][n - 1]; }这个解法思路很巧妙但有一个现实问题它修改了函数入参可能影响外层调用方生产环境里不建议这么做。在面试中可以作为“额外加分的头脑风暴”提出来然后说明工程上的顾虑反而显得你考虑周全。4. 同类题拓展一道题带出一类 DP 套路4.1 路径类 DP 的四步法刷完这道题你应该提炼出一套可复用的思考流程遇到路径类 DP 先按四步走定义状态想清楚 dp[i][j] 表示什么通常是“从起点到当前格子的某种最优值或计数”。写转移方程列出所有可能一步走到当前格子的前驱状态按题意取 min、max 或求和。初始化边界把没有前驱状态的位置单独处理一般是第一行、第一列或起点。确定遍历顺序保证计算某个状态时依赖的状态已经被算出来。网格场景通常是从左上到右下。这套流程几乎可以套用到所有网格路径题区别只在于状态含义和转移方式。4.2 和“不同路径”系列的对比LeetCode 62“不同路径”是这个系列的入门题它求的是一共有多少条路径状态转移是 dp[i][j] dp[i-1][j] dp[i][j-1]加法对应“方案数合并”。LeetCode 63“不同路径 II”在上面加了一个障碍条件初始化时遇到障碍要置零转移时跳过障碍格。64 则是把“方案数”换成了“最小路径和”于是加法变成了取 min 再加当前格子的值。这三道题用的是同一个网格模型但考察点完全不同。把 64 吃透顺手把 62、63 一起做了你就会发现 DP 的“套路感”很强换汤不换药。4.3 面试现场怎么从基础解讲到最优解在面试中这类题的演示路径通常是先说暴力 DFS 为什么慢再给出二维 DP最后主动提出滚动数组优化。这是一套很自然的“由浅入深”节奏既证明你理解了本质又展示了优化意识。我见过不少候选人一上来就写滚动数组结果写错方向反而翻车。稳妥做法是先写二维 DP跑通之后再说“这个解法空间可以继续压缩因为转移只依赖上一行”然后现场改成一维。面试官会更看重你的思维过程而不是你背了多少模板。另外如果面试官问“能不能用贪心”你要能立刻反驳每一步选择当前向右或向下中较小的数字不能保证全局最优因为局部选择会改变未来的可选集合。例如下面这个网格| 0 | 1 | 100 | | 2 | 100 | 100 | | 2 | 2 | 2 |贪心从起点向右走因为 1 比 2 小结果一路撞上两个 100总和 203而先向下走的路径总代价只有 8。这个反例能快速说明贪心不成立。5. 常见错误、调试方法与实践心得5.1 从超时到 AC初学者的升级路线我第一次做这道题时第一反应是写 DFS代码很短跑小样例也没问题结果一提交就超时。后来画了一下递归树才明白大量路径在中间格子上反复交汇重复计算的子问题指数级膨胀。这个顿悟时刻很重要遇到最优路径、方案计数、可行性判断如果暴力搜索里存在大量重叠子问题就应该立刻往动态规划方向想而不是死磕剪枝。剪枝确实能提升 DFS 的效率但对 200×200 的网格来说剪枝救不了组合爆炸。DP 的核心竞争力不是“更快地重复计算”而是“根本不重复计算”。5.2 高频 Bug 排查速查表症状原因修复方法结果比预期小尤其首行首列不对忘记把起点 grid[0][0] 计入 dp[0][0]初始化 dp[0][0] grid[0][0]第一行或第一列结果错误在边界位置直接套用转移方程访问了不存在的格子提前初始化第一行第一列或在转移时用无穷大屏蔽不存在方向滚动数组整体结果错乱更新顺序写反从右往左更新了改为从左往右更新保证 dp[j-1] 是当前行值滚动数组第一列结果停留旧值每轮第 0 列没有单独累加在每轮开始时执行 dp[0] grid[i][0]空输入直接报错没有处理 grid 为空或长度为 0开头加 if (grid null原数组被修改后结果奇怪原地写法中读取顺序不合理按从左到右的顺序更新并在读取原值前完成计算这里特别强调一下滚动数组的调试经验纸上画两行格子第一行标“上一行的旧值”第二行标“将要写入的新值”然后用笔模拟更新过程。我敢说绝大多数人只要亲手画一次就再也不会把更新方向写反。5.3 打印 DP 表这个小习惯很值钱刷动态规划题时打印中间状态能极大提升调 Bug 效率。二维 DP 阶段可以写一个简单的打印函数每次循环结束输出当前 dp 表滚动数组阶段每轮更新后打印一维数组观察它如何从“上一行”逐渐变成“当前行”。private void print(int[][] dp) { for (int[] row : dp) { System.out.println(Arrays.toString(row)); } }def debug_print(dp): for row in dp: print(row)我在做其他网格类 DP 题时也常靠这招一眼就能看出是哪一行哪一列错了比盯着代码干想要快得多。另一个小技巧是先用极小的测试用例比如 2×2 或 3×3跑通逻辑再切到全量用例能省下很多无谓的调试时间。这道题刷到滚动数组版本就算真正吃透了。它把一个完整 DP 解题流程浓缩在一个简单的例子里尤其是“状态定义如何服务于转移”和“如何安全地压缩空间”这两个点后续做更多复杂 DP 题还会反复遇到。我个人在实际带新人时几乎都会先让他们把 64 的二维和解滚动数组两个版本各写一遍再继续往下刷。把这里踩过的坑记牢后面遇到背包、区间 DP 时你会感谢现在认真抠过细节的自己。