前阵子有位读者私信我说他在准备算法面试时被一道“m*n矩阵中不同路径”难住了写完递归之后等了好几分钟都算不出结果后来换成动态规划又卡在初始化上。我让他顺手把“最小路径和”也做了结果他惊讶地发现这两道题几乎是同一个模子。这也是我在日常帮别人看代码时最常遇到的情况——很多初学者以为动态规划是一套高深莫测的魔法实际上只要你把状态定义写清楚、递推关系弄明白大部分路径类问题都能用一个统一的模型解决。这篇文章我会用最直白的方式拆解这两个经典问题如何从暴力递归进化到记忆化搜索再改造成二维 DP最后压缩成一维滚动数组。整个过程不绕弯、不堆术语每一步我都给出可复现的代码和手算过程。不管你现在是刚接触 DP 的新手还是已经刷过不少题但总在细节上翻车这篇内容应该都能帮你把这类问题彻底理清。1. 为什么这两个问题总被放在一起讲都是“格子间移动”的决策模型先别急着写代码我们试着把问题翻译成“人能看懂的话”。不同路径的问题描述一般是一个机器人从左上角出发每次只能向下或向右移动一格问到达右下角一共有多少条不同的路径。最小路径和则是在同一个网格里每个格子上有一个数字机器人从左上角走到右下角同样只能向下或向右问路径上数字之和最小是多少。这两道题被放在一起不是因为它们长得很像而是因为它们共享同一个决策模型机器人站在某个格子 (i, j) 时下一步只能往右走到 (i, j1)或者往下走到 (i1, j)。也就是说如果我们反过来想要到达格子 (i, j)机器人只有两种可能的来源——从上方 (i-1, j) 过来或者从左边 (i, j-1) 过来。在这个模型下路径问题天然具有“重叠子问题”和“无后效性”到达某个格子的方式只取决于它上方和左方格子的状态和更早怎么走的无关。这就是动态规划能够发力的地方。很多教程喜欢一上来就抛状态转移方程搞得大家一头雾水。其实你只要记住一句口诀“每个格子的答案是由它上面和左边的答案拼出来的”后面所有推导都顺理成章。1.1 先把问题翻译成状态图我在给朋友讲解的时候最喜欢画一张 3×3 的网格把每个格子看成图中的一个节点。从左上角到某个节点的路只能来自它的上邻居和左邻居。于是整个问题就变成了一个有向无环图每个节点的入度最多为 2。不同路径问题是在这个图上数从起点到终点的路径数量最小路径和则是在这个图上找一条总权值最小的路径。一旦有了这个视角动态规划的三个关键要素就清晰了状态dp[i][j] 表示“从起点走到 (i, j) 的某种结果”至于是路径数还是最小和看题目要求。转移dp[i][j] 由 dp[i-1][j] 和 dp[i][j-1] 两者导出。初始化起点 (0,0) 的值要单独设置第一行和第一列因为没有“上方”或“左方”来源需要特殊处理。这个模型能解释的还不止这两道题。如果把网格换成棋盘、地图、二维数组把移动规则从“向右向下”改成“四个方向”甚至把数字换成概率核心思路依然通用。这也是为什么我建议路径类 DP 优先从这种“状态图”开始思考而不是死记代码。1.2 共同的递推骨架从上边来 从左边来把两个问题放在一起对比你会发现它们的状态转移方程长得几乎一模一样不同路径dp[i][j] dp[i-1][j] dp[i][j-1]最小路径和dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])唯一的区别只是“合并方式”一个是加和因为要累计所有到达该格子的方案数另一个是取 min因为要选择代价更小的那一条路。换句话说动态规划本身只是一个框架真正决定问题性质的是你对“结果”的定义和对“合并”的选择。很多人会在这时候问为什么不能从左上角递归到右下角其实完全可以只是纯递归会有大量重复计算。比如计算 (2,2) 时会去计算 (1,2) 和 (2,1)而 (1,2) 又要计算 (0,2) 和 (1,1)这里面 (1,1) 被重复计算的次数呈指数增长。这就是动态规划最核心的价值——把每个子问题的解存起来避免重复劳动。理解了这一点后面看代码就会觉得非常自然。2. 不同路径计数型DP的完整推导从递归到填表不同路径是一个典型的计数问题。所谓“不同路径数”本质上是把走到每个格子的方案全部加起来。我建议先写一个最暴力的递归版本哪怕它超时也没关系因为它能帮助我们看清问题结构。def unique_paths_naive(m, n): def dfs(i, j): # 越界视为0 if i 0 or j 0: return 0 # 起点算1条路径 if i 0 and j 0: return 1 return dfs(i - 1, j) dfs(i, j - 1) return dfs(m - 1, n - 1)这个写法直白到不能再直白想到达 (i, j)就先到达它上方或左边然后把两条路径数量相加。但当你输入 m20, n20 时这段代码基本就跑不完了。问题出在大量的重复调用dfs(1,1) 会被 dfs(1,2) 和 dfs(2,1) 分别调用一次而它们各自又会继续调用相同的子问题。2.1 先写暴力递归看它重复计算在哪里为了更直观地感受重复计算我拿 m3, n3 的调用关系举例。你要计算 dfs(2,2)它会去算 dfs(1,2) 和 dfs(2,1)。dfs(1,2) 会算 dfs(0,2) 和 dfs(1,1)dfs(2,1) 会算 dfs(1,1) 和 dfs(2,0)。你看dfs(1,1) 被算了两次。随着网格边长增加这个重复量会爆炸式增长因为每个非边界的格子都会反复出现在大量递归分支里。解决方式有两种一是用字典或数组做记忆化把算过的 dfs(i,j) 存起来二是直接改成自底向上的循环这也正是动态规划的标准做法。记忆化搜索本质上还是递归但能保证每个子问题只算一次而 DP 用的是迭代填表逻辑上更显式。两者时间复杂度都是 O(m*n)但在工程实现上迭代 DP 通常更少受递归栈深度影响所以我更推荐初学者先掌握填表法。2.2 用3×3网格手推一遍DP表我们手推一个 3×3 的网格看看 dp 表是怎么一步步填满的。先初始化起点 (0,0) 的路径数是 1。第一行 (0,1) 和 (0,2) 只有一条路能到就是从左边一路走过来所以全是 1。同理第一列 (1,0) 和 (2,0) 也只有一条路所以也全是 1。初始表如下dp[i][j]j0j1j2i0111i11??i21??现在按行从上往下填。i1, j1 时它的上方 dp[0][1]1左边 dp[1][0]1所以 dp[1][1] 11 2。i1, j2 时上方 dp[0][2]1左边 dp[1][1]2所以 dp[1][2] 12 3。接着填 i2 这一行dp[2][1] dp[1][1] dp[2][0] 21 3dp[2][2] dp[1][2] dp[2][1] 33 6。所以 3×3 网格的不同路径总数是 6。你可以用穷举法验证从左上角到右下角每一步只能向右或向下总共需要走 2 步右、2 步下排列组合数是 4!/(2!2!)6。和 DP 结果一致。这个手算过程虽然简单但它能让你直观看到“每一格只依赖上方和左方”这一点这正是后面做空间优化的基础。2.3 第一行第一列初始化为什么要置1初始化阶段最容易出错。我见过不少同学把 dp 数组全部初始化为 0然后从 (0,0) 开始递推结果第一行和第一列永远是 0答案自然不对。为什么第一行第一列必须是 1因为机器人只能向右和向下移动所以它到达第一行任意格子的路径只有唯一一条一直向右。第一列同理只有一直向下这一条。如果我们在循环里直接dp[i][j] dp[i-1][j] dp[i][j-1]对于 i0 或 j0 的格子会出现下标越界。因此要么单独初始化首行首列要么在循环里加边界判断。更优雅的做法是让 dp 数组多开一圈但那样定义状态时就要偏移代码可读性略差。我个人习惯是直接初始化首行首列逻辑清晰也不容易出现 bug。下面是二维 DP 的完整代码def unique_paths(m, n): dp [[0] * n for _ in range(m)] # 初始化第一行和第一列 for j in range(n): dp[0][j] 1 for i in range(m): dp[i][0] 1 for i in range(1, m): for j in range(1, n): dp[i][j] dp[i-1][j] dp[i][j-1] return dp[m-1][n-1]这段代码的时间复杂度是 O(m*n)空间复杂度也是 O(m*n)。对于 m 和 n 几百左右的问题完全够用。但如果你有空间洁癖或者面试官追问“能不能把空间优化到 O(n)”那就要用下一章的滚动数组思路了。3. 最小路径和从“数方案”变成“选最优”DP只是换了个算子最小路径和看起来只是把加法换成 min但很多人会在状态定义上犯迷糊。我们沿用同一个网格模型机器人到达 (i, j) 时不管之前走的哪条路到达该格子的路径和一定等于它上一个格子的路径和加上当前格子数值。而上一个格子只有可能是 (i-1, j) 或 (i, j-1)。为了让总路径和最小我们当然选择两者中较小的那个。这就是“最优子结构”局部最优的组合能导出全局最优。注意这里的状态含义变成了“从起点到达当前格子的最小路径和”而不是“方案总数”。所以转移方程写作dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])如果你只记住了不同路径的加法到这里可能反应不过来为什么要 min想象你在走山路走到某个岔路口时你只需要知道两条路哪条更省力然后选它。每个格子的决策都是独立的不会影响后续的“能不能走”因为无论是从上边来还是从左边来你到达 (i,j) 之后下一步往右或往下的选择都一样。这种情况下min 就是最自然的合并操作。3.1 先写暴力递归看它重复计算在哪里为了验证状态定义我们同样可以先写一个递归版本def min_path_sum_naive(grid): m, n len(grid), len(grid[0]) def dfs(i, j): if i 0 and j 0: return grid[0][0] if i 0 or j 0: return float(inf) return grid[i][j] min(dfs(i - 1, j), dfs(i, j - 1)) return dfs(m - 1, n - 1)这里越界返回无穷大是为了让 min 选择另一条有效路径。但因为重复计算这个递归同样效率低下。给每个格子套一个记忆化就能看出它其实和不同路径的递归没有本质区别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 0 and j 0: return grid[0][0] if i 0 or j 0: return float(inf) return grid[i][j] min(dfs(i - 1, j), dfs(i, j - 1)) return dfs(m - 1, n - 1)很多人在写递归时会把起点写成return 0那是对“路径数”的理解最小路径和必须返回起点本身的值因为路径至少包含起点格子。这一步出错会导致所有结果差一个 grid[0][0]。3.2 手算一个4×4网格的表格我们用一个具体的 4×4 网格来填表这样你能看到递推是如果一步一步推进的。假设网格值如下grid列0列1列2列3行01315行12824行23491行36572第一步初始化 dp[0][0] 1。第一行只能从左边一路累加dp[0][1]134dp[0][2]415dp[0][3]5510。第一列只能从上边一路累加dp[1][0]123dp[2][0]336dp[3][0]6612。然后从行1列1开始填(1,1)grid8上方 dp[0][1]4左方 dp[1][0]3取较小值3加上8得 11。(1,2)grid2上方 dp[0][2]5左方 dp[1][1]11取5加2得 7。(1,3)grid4上方 dp[0][3]10左方 dp[1][2]7取7加4得 11。继续(2,1)grid4上方 dp[1][1]11左方 dp[2][0]6取6加4得 10。(2,2)grid9上方 dp[1][2]7左方 dp[2][1]10取7加9得 16。(2,3)grid1上方 dp[1][3]11左方 dp[2][2]16取11加1得 12。最后(3,1)grid5上方 dp[2][1]10左方 dp[3][0]12取10加5得 15。(3,2)grid7上方 dp[2][2]16左方 dp[3][1]15取15加7得 22。(3,3)grid2上方 dp[2][3]12左方 dp[3][2]22取12加2得 14。所以这个网格的最小路径和是 14。你可以自己沿路径验证1 → 2 → 3 → 4 → 2 → 1 → 2正好是 14。这个手算过程想说明的是DP 表里每个格子存的是“到当前格子的最优值”它并不关心你是从哪条路来的真正有用的信息只有上方和左方两个候选值。3.3 网格里有负值、零值时方法还成立吗有读者问如果网格里出现负数和零min 还适用吗答案是适用。因为机器人只能向右向下不能往回走路径长度是固定的 mn-2 步。负值只会让某些路径的“成本”变低但 DP 仍然会从上方和左方选择更小的那个。如果有零只是不增加成本不影响递推逻辑。真正需要注意的场景是如果允许上下左右任意移动那就不能再按这个 DP 了因为会出现回环和无限路径问题需要改用更复杂的图算法。另外如果题目要求“必须走完所有格子”或者“路径长度有额外限制”那状态就要加上更多维度比如步数或剩余步数。这已经超出了今天讨论的范围但你要知道核心模型的边界在哪。4. 空间优化到底怎么想出来的一行数组滚动的完整推导二维 DP 虽然好懂但 m 和 n 一旦到几千O(m*n) 的空间可能会让内存告急。尤其是面试官经常追问“能不能不用二维数组”这时候你就得明白空间优化的推导过程而不是背结论。我们回头看一看递推表计算 dp[i][j] 时只用到了当前行的左边一个 dp[i][j-1] 和上一行的同列一个 dp[i-1][j]。这意味着当我在填第 i 行时第 i-2 行及之前的所有数据都不会再被用到。因此我们完全可以用一维数组 dp[j] 来滚动保存状态在进入新一行前dp[j] 存的是上一行第 j 列的值进入新一行后从左到右更新 dp[j]更新后的值就是当前行的值。4.1 从依赖关系看哪些数据可以扔掉还是以最小路径和为例。设dp[j]在更新前表示“上一行到第 j 列的最小路径和”。当我们更新dp[j]时有两个来源从上方来就是旧值dp[j]上一行算出的结果。从左边来需要当前行已经更新过的dp[j-1]。如果我从左到右循环那么执行到 j 时dp[j-1] 已经更新为当前行的值dp[j] 还是上一行的值。于是新dp[j] grid[i][j] min(dp[j], dp[j-1])一行代码就完成了二维 DP 中“上方”和“左方”两个信息的合并。更新完成后dp[j] 就变成了当前行的值供下一列使用。不同路径同理dp[j] dp[j] dp[j-1]等式右边的 dp[j] 还是上一行到当前列的方法数dp[j-1] 是当前行已更新的左方案数。这样我们就把空间直接从 O(m*n) 压缩到 O(n)。4.2 正序更新与逆序更新最容易踩的坑滚动数组中一个绕不过去的坑是更新方向。拿不同路径来说我们是在一维数组里正着从左往右更新因为需要当前行左侧的新值来参与计算。如果你反过来从右往左更新那么 dp[j-1] 还是上一行的旧值计算就会出错。这一点和背包问题里的“逆序更新”正好相反很多同学在这里被搞晕。判断方法很简单写出依赖关系。如果某一维的更新会用到当前行已经计算好的值就必须保证那个值已经被更新。比如不同路径依赖 dp[j-1] 这个“左侧”值左到右正序能让它先生效如果依赖的是“右侧”值那就要右到左。不要死记画一下状态依赖就能立刻明白。下面是两个问题的一维滚动版本可以直接拿去用def unique_paths_1d(m, n): dp [1] * n for i in range(1, m): for j in range(1, n): dp[j] dp[j] dp[j-1] return dp[-1] def min_path_sum_1d(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) dp [float(inf)] * n dp[0] 0 for i in range(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]注意min_path_sum_1d里 dp 初始化为无穷大dp[0]0这样第一行第一列的值会在循环中被累加。每一行的 dp[0] 单独处理是因为它只有上方来源没有左侧来源。如果你不想处理 dp[0] 的边界也可以用二维 DP 写但既然选择了空间优化边界处理就必须格外小心。4.3 一行代码对比二维DP和一维DP很多人觉得一维版本“看不懂”其实只要把二维 DP 的代码和一维放在一起对比就很容易理解二维dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])一维dp[j] grid[i][j] min(dp[j], dp[j-1])唯一的区别是一维里dp[j]在赋值之前代表dp[i-1][j]赋值之后代表dp[i][j]。可以说一维数组是“原地更新”而二维数组是“全量保留”。时间上两者没有差异都是 O(m*n) 次操作但一维的空间复杂度从 O(m*n) 降到了 O(n)。我在实际编码时会先用二维版本跑通再手动改成一维。因为二维版本的代码更不容易出错调试起来也直观。确认逻辑正确后再根据面试官要求做空间优化。这样做看似多花一步实际上能帮你省掉大量调试时间。5. 变体、实战和我的自检清单动态规划一旦形成框架最怕的是遇到变体就发怵。其实路径类问题的常见变形大多是在原模型上加一些限制比如障碍物、可变移动方向、权重变化等。掌握好这个核心模型你就能迅速迁移。5.1 加了障碍物、改变了移动方向怎么办如果网格中某些格子不能走也就是“障碍物”我们只需在状态转移时加一个判断遇到障碍物该格子的路径数或最小路径和直接置为 0对计数题或无穷大对最值题表示不可达或不可选。比如不同路径 II 中dp[i][j] 0 if obstacle[i][j] 1 else dp[i-1][j] dp[i][j-1]。初始化时如果第一行或第一列有障碍物那么障碍物之后的格子全部不可达都要置 0。如果移动方向从“只能向右向下”改成“可以向下也可以向右还可以斜着走”那只会在递推公式里多几个来源项比如dp[i][j] dp[i-1][j] dp[i][j-1] dp[i-1][j-1]但模型本身不变。如果改成“可以上下左右走”那就不是简单的 DAG 了因为可能出现循环需要用 Dijkstra 这类图算法而不是 DP。所以动手前先看清楚题目限制非常重要。5.2 组合数学解法与DP的取舍不同路径还有一种数学解法从左上角到右下角无论怎么走总共需要向右 m-1 步、向下 n-1 步总共走 mn-2 步。路径数就是从这 mn-2 步中选择哪 m-1 步向右即组合数 C(mn-2, m-1)。这个公式非常优雅但有几个问题一是当 m、n 很大时组合数计算容易溢出 int通常需要边计算边约分或使用大数类型二是如果题目加上障碍物组合数学会变得极其复杂。DP 则能自然处理障碍物、权重等变体所以从通用性上来说我强烈建议大家把 DP 作为主解法组合数学可以作为验证答案的手段。比如前面 3×3 的例子里DP 算出来是 6组合数 C(4,2)6两边一致你就能对代码更放心。5.3 我踩过的坑和自检清单讲几个我实际编码中栽过跟头的地方也是我在帮别人 review 代码时最常发现的几类问题。第一初始化顺序错乱。不同路径里第一行、第一列全置 1但如果第一行某个格子是障碍物那就不是无脑置 1 了必须从障碍物开始变成 0。很多同学把“全都是 1”当成固定套路遇到变体就翻车。第二滚动数组遍历方向想当然。比如不同路径的 1D 版本从左到右更新是没有问题的但如果题目变成从右下角往左上角走更新方向就会变。遇到新题一定要先画出依赖关系。第三最小路径和里忘记加grid[i][j]。状态定义是“路径和”不是“到了这一步的选择数”漏加当前格子值会让结果整体变小。第四处理空网格。grid可能为空或grid[0]为空很多刷题新手没做防护直接grid[0][0]崩一地这个基本功必须养成。我给自己定了一个自检清单状态定义是否清楚、边界条件是否覆盖、递推方向是否依赖已更新值、返回结果是 dp[m-1][n-1] 还是 max/min 某一列。每次写完代码用这几个问题过一遍能避免绝大部分低级错误。最后再说一个经验遇到这类题目不要急着写代码。先动手画一个 3×3 或 4×4 的例子把 dp 表格手填一遍然后观察转移依赖。这个过程能让你少走很多弯路。我过去带过的一位朋友最初就是靠这个“画表—填表—找依赖”的方法从看到 DP 就头疼到后来能在几分钟内写出滚动数组解法。你也不妨试试。