矩阵路径问题放在动态规划的练习序列里几乎就是为“无后效性”和“最优子结构”这两个概念量身定做的入门台阶。我刚开始刷这类题时最常见的反应是这不就是一个二叉树的展开吗每一步不是向下就是向右枚举所有路径不就行了。真正动手把状态表画出来以后才发现自己对 DP 的理解还停留在“递归加缓存”的层面根本没有掌握“填表”这个核心动作。这篇文章是动态规划系列的第二篇我会专门把矩阵路径这一类问题讲透从最基础的网格走路说起依次拆解状态定义、转移方程、边界条件、滚动数组再带障碍物和最小路径和这两个最常见的变形。它适合已经会写基础递归、想彻底搞懂动态规划表格怎么来的读者如果你只是听过“动态规划”四个字这篇也能当做一个很直观的切入点。1. 矩阵路径的问题模型先把题目翻译成状态1.1 这一家族里最常考的三副面孔其实“矩阵路径”在题库里长得不完全一样但核心是同一套东西。最基础的问题是路径计数一个 m 行 n 列的网格从左上角出发只能向右或向下走问到达右下角一共有多少条不同路径。第二个常见形态是带权路径每个格子有一个数字路径的代价是经过格子数字的总和问最小代价是多少这类题目通常叫最小路径和。第三个形态是在路径计数的基础上增加障碍物某些格子不能走问有多少条合法路径。这三种形态看起来很像但状态定义和转移方程相差不小。我见过不少同学把计数题的模板直接套到最小路径和上最后发现边界初始化完全对不上。所以拿到题目先不急着写代码先用一句话把问题说清楚终点是哪个格子每一步允许做什么最后要的是方案数还是极值1.2 一张二维表就是整个问题的坐标系动态规划里最抽象的其实是“状态”这两个字。很多讲稿上来就写 dp[i][j] ...读者看是看懂了但始终不知道这张表是怎么被想到的。矩阵路径的好处就在于它天然提供一个坐标系横坐标是列 j纵坐标是行 i每一个格子恰好对应一个问题的小状态。把整个问题拆成格子来思考有一个非常实际的收益你不必再关注“具体的路线长什么样”只需关心“每个格子上的答案是多少”。由于被划分后的格子天然具有顺序性我们从左上角开始一格一格地填后面的答案总能从前面几个方向汇总出来。这比在脑子里同时跟踪几十条路径要直观太多。我自己在讲这类题时经常说不要去想路线去想格子每个格子都回答“从起点到我这有多少种方法/最小代价是多少”整张表填完答案自己就出来了。1.3 为什么无后效性在这里天然成立矩阵路径中的“无后效性”其实很好理解。从起点走到 (i,j)接下来无论选择向右还是向下都只跟“当前在哪个格子”有关跟你之前走的是蛇形还是直线没有任何关系。这种性质让子问题可以被安全地合并只要计算出到达每个格子的答案后面格子就可以单独依赖它不需要知道这个答案是怎么得到的。与之相对的如果题目要求“路径不能重复经过格子”或者“路径必须按特定顺序经过某些点”那就不是普通 DP 能直接处理的了这些点也是做题时判断模型适用范围的重要信号。2. 状态定义与转移方程填表之前必须想明白的两件事2.1 dp[i][j] 到底代表什么以最经典的统计路径数为例。网格大小 m 行 n 列起点在左上角 (0,0)终点在右下角 (m-1,n-1)每次只能向右或者向下。定义 dp[i][j] 表示从起点出发到达格子 (i,j) 的不同路径数量。这个定义听起来简单却有一个非常容易被忽略的坑dp[i][j] 代表的是“方案数”不是“步数”。如果你不小心定义成步数就会发现在这个网格模型里从起点到任意格子的步数几乎是固定的等于 ij根本携带不了任何区分路径的信息。那状态就彻底失效了。所以定义状态时一定要想清楚变量要承载的信息是什么——方案数、代价、可行性这些不一样。2.2 转移方程是从“最后一步”倒推出来的要到达 (i,j)最后一步只有两种可能从上方 (i-1,j) 向下走或者从左边 (i,j-1) 向右走。这两种情况互斥而且覆盖了所有可能的到达方式。于是到达 (i,j) 的路径总数等于到达上方格子的路径总数加上到达左边格子的路径总数dp[i][j] dp[i-1][j] dp[i][j-1]这个式子值得多说几句。它其实是用“分类加法计数原理”在做组合计数把到达当前格子的所有路径按最后一步的方向分成两类两类之间没有重叠加总就是全部。这也是为什么动态规划能避免重复枚举——每一条路径都在状态表中被记过一次又只被记过一次。初次接触这个式子的同学常会问为什么不加一个“1”之类的东西。原因是从 (i-1,j) 走到 (i,j) 那“一步向下”没有产生新的走法分支它只是把原来的路径延续了一下同理从左边延续过来也是一样。因此方案数没有新增项只是两个前驱状态的汇合。2.3 边界条件整张表的源头在这接下来是填表之前必须定下来的初始值。第一行 dp[0][j] 是多少从起点横着一直往右走只有一种方式可以到达第一行的任意一个格子所以第一行全部是 1。第一列同理只有一种方式能一直向下走到 (i,0)所以第一列也全部是 1。这里犯的最多的错误是把第一行、第一列都初始化为 0然后在循环里用 if 特殊处理。如果处理顺序不对先判断 i0 就会把第一行整个设成 1再继续向右累加最后也能算出来怕的是循环写得太随意导致第一行使用了 dp[i][j-1] 而 dp[i][j-1] 又正好没被初始化连报错都没有答案就悄悄错了。更稳妥的做法是在递推开始前单独把第一行和第一列先填好。特别强调一个很多人会忽略的点dp[0][0] 必须等于 1。它表示起点本身就有“一条空路径”是所有路径的最初来源。如果把 dp[0][0] 设为 0后面所有格子的路径数都会是 0整个 dp 表直接废掉。2.4 一个最小的完整实现def unique_paths(m: int, n: int) - int: # 初始化 dp 表第一行和第一列默认都是 1 dp [[1] * n for _ in range(m)] 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]这段代码看着很短但承载了状态定义、转移方程和边界条件三个要点。外层循环按行从上到下内层循环按列从左到右。为什么这个遍历顺序是对的因为计算 dp[i][j] 需要用到 dp[i-1][j]上一行已经算完和 dp[i][j-1]本行左边刚算完只有按行从上到下、列从左到右才能保证两个依赖都已就绪。复杂度也很清晰每个格子都计算一次时间 O(mn)使用二维表存所有状态空间 O(mn)。这只是一个起点下一节我会把它压到一维。3. 空间优化从二维表到滚动数组3.1 为什么可以滚起来回到转移方程dp[i][j] 只依赖两个前驱上一行的 dp[i-1][j]以及本行左边的 dp[i][j-1]。也就是说在我们填充第 i 行的时候手里的表格其实只需要两行一行是当前行正在被更新另一行是上一行负责提供 dp[i-1][j]。至于更早的第 i-2 行、第 i-3 行它们已经不会再被任何后续状态使用留在内存里完全是浪费。这个观察给了我们一个很自然的优化方向用一个长度 n 的一维数组替代整个二维表。数组的某个位置 dp[j] 在更新之前代表上一行的第 j 列在更新完成之后变成当前行的第 j 列。每一轮外层循环结束后这个数组自然“升级”成了新的上一行供下一轮使用。3.2 覆盖顺序是关键不能倒着来一维更新的核心代码是def unique_paths(m: int, n: int) - int: dp [1] * n for i in range(1, m): for j in range(1, n): dp[j] dp[j-1] return dp[n-1]注意内层循环的 j 从小到大。为什么在更新 dp[j] 时右侧表达式用到的 dp[j] 是上一行的值dp[j-1] 是本行已经更新好的值。两者一加正好得到 dp[i][j] dp[i-1][j] dp[i][j-1]。这里 j 从小到大非常关键因为 dp[j-1] 必须先于 dp[j] 被更新成“当前行”的值。如果改成 j 从 n-1 往下到 1会发生什么dp[j] 会用到还未更新的 dp[j-1]此时 dp[j-1] 还是上一行的值实质就变成了 dp[i-1][j] dp[i-1][j-1]相当于用了旧一行的两个格子结果完全错误。这个坑我实际踩过在写最小路径和的滚动数组时不注意就倒序更新最后样例结果越算越大打印中间表才定位到覆盖方向。所以每次写滚动数组我都会在心里默念一遍正序从左到右先更新左边再更新右边。3.3 空间复杂度的最终结果滚动数组把空间从 O(mn) 降到 O(n)。如果输入的网格是 m 行 n 列那么只需要一个长度 n 的一维数组。有些题目给的网格是长条形的比如 m10000、n3滚动数组省下的内存就很可观。时间上依然是 O(mn)因为你还是要把每个格子都扫一遍这个复杂度是下限不太可能再低。另外提醒一个细节上面的代码默认第一行全是 1所以 dp 数组初始化成全 1。如果题目换成了带障碍物或带权重的版本初始化就不能这么粗暴了要结合题目把第一行第一列的累积值算好。这也是为什么我建议先理解二维版本再写滚动数组直接背一维模板遇到变形题很容易在边界上翻车。4. 经典变形实战障碍物与最值路径4.1 带障碍物每一步都要先回答“能不能走”在统计路径数的基础上题目会增加一个障碍物网格1 表示这个格子不能进。状态定义依然不变dp[i][j] 表示从起点到 (i,j) 的方案数。转移时却有额外条件先看当前格子是否可达。如果 obstacleGrid[i][j] 是 1那么 dp[i][j] 直接置 0否则才执行常规转移。def unique_paths_with_obstacles(obstacleGrid): m, n len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] 1: return 0 dp [[0] * n for _ in range(m)] dp[0][0] 1 # 第一列遇到障碍物后后面的格子都不可达 for i in range(1, m): if obstacleGrid[i][0] 1: break dp[i][0] 1 # 第一行同理 for j in range(1, n): if obstacleGrid[0][j] 1: break dp[0][j] 1 for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j] 1: dp[i][j] 0 else: dp[i][j] dp[i-1][j] dp[i][j-1] return dp[m-1][n-1]这里最隐蔽的陷阱就在第一行和第一列。障碍物出现在第一行时它右侧的所有格子都不可能再到达因为路径只能向右走没有别的绕法。同理第一列出现障碍物后它下方的所有格子也全部不可达。所以初始化用 break 直接截断比逐格判断更清晰。还要考虑起点和终点本身是障碍物的情况。如果起点 (0,0) 是障碍直接返回 0因为根本不能出发。终点如果是障碍循环最后自然会给它填 0逻辑上没问题不过显式判断一下会更安心。4.2 最小路径和为什么不能每一步都选小的最小路径和的题目一般长这样给定一个 m×n 的网格每个格子有一个非负数字路径只能向右或向下问从左上到右下经过路径数字的总和最小是多少。这个问题的状态定义变成 dp[i][j] 表示从起点到 (i,j) 的最小代价转移方程是dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]边界条件比计数题复杂一些第一行的每个格子只能从左边过来所以 dp[0][j] dp[0][j-1] grid[0][j]第一列同理只能从上边下来dp[i][0] dp[i-1][0] grid[i][0]。这两句写错是常见的丢分点很多同学直接套计数题的“全部设成 1”答案自然不对。一个经常被问到的问题是为什么不能用贪心每一步都选择右边和下边里数字较小的那个格子我拿一个 3×3 的例子说明1 3 1 1 5 1 4 2 1如果从左上角出发右边的格子是 3下边的格子是 1贪心会选择向下。接着在 (1,0)右边是 5、下边是 4贪心又选择向下。走到 (2,0) 后只能向右经过 2 和 1总代价 1 1 4 2 1 9。但最优路径其实是从第一行绕过去1 - 3 - 1 - 1 - 1总代价是 7。这个例子告诉我们路径数字大还是小要放到整条路径的上下文里看只看眼前的一步可能被一个局部陷阱带偏。DP 的价值就是让每一步的决策都基于全局最优的子结构。手动填一遍 dp 表也能更好地理解。先把第一行列算出来第一行累加为 1、4、5第一列累加为 1、2、6。然后从 (1,1) 开始dp[1][1] min(dp[0][1], dp[1][0]) 5 min(4,2)5 7按这个规则填完整张表终点处的值就是全局最小代价。这个手算过程其实也是在训练“从子结构看问题”的直觉。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 i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j] return dp[m-1][n-1]同样的滚动数组思想在这里依然适用把二维表换成一行数组即可唯一要注意的还是边界初始化。4.3 怎么快速识别一道变形题能不能用这个模型并不是所有矩阵题目都适合 DP。我的经验是拿到一个网格移动类题目后先默问三个问题。第一是否存在重叠子问题同一个格子是否会被多条路径反复访问如果会就说明递归会重复计算值得用状态表缓存。第二是否存在最优子结构到达某个格子的答案能不能由它的上、左两个前驱格子的答案直接推导。第三是否满足无后效性到达当前格子之后未来的决策是否只取决于“我在哪个格子”而不取决于我之前走过的具体路线。三个答案都是“是”基本就可以放心写 DP 了。如果题目中出现“路径不能重复经过节点”“必须按特定顺序访问一系列关键点”这样的限制那麻烦就大了因为状态里不只要记录当前位置还得记录已经走过哪些点这会让状态维度爆炸不是普通二维 DP 能解决的需要回到状态压缩或图上搜索的思路。做题时先确认问题复杂度再决定用什么工具能省很多无用功。5. 常见错误与调试套路我踩过的坑一次性告诉你5.1 一张表看懂高频错误错误现象可能的根因解决办法结果总比预期少很多第一行或第一列初始化成 0先把边界行填好再进主循环结果比预期大或者出现奇怪数值滚动数组倒序遍历用了旧行数据把内层循环改成从 1 到 n-1 正序带障碍物时起点或终点返回错误没判断 (0,0) / (m-1,n-1) 是否为障碍函数开头先处理起点返回前检查终点大样例返回负数或溢出路径数超过 int 上限用 64 位整数类型必要时每一步取模最小路径和结果对不上边界行/列没有做累加单独初始化 dp[0][j] 和 dp[i][0] 为累加值dp[0][0] 初始值错误设为 0导致整张表为 0计数题起点必须为 1这里特别想强调一下溢出的问题。不同路径的总数随网格尺寸增长得很快一个 20×20 的网格路径数量就已经远超普通 32 位整形的范围了。语言检查时注意用 64 位类型如果题目还要求取模那在每次加法后立即取模不要等最后再一次取否则中间值可能已经爆掉。Python 占了大整数计算的优势但如果写 C 或 Java这是必须升级的意识。5.2 调试技巧把 dp 表打出来看很多 DP 题目光在脑内推流程是很痛苦的尤其是矩阵类。我的调试习惯是在小尺寸用例上把 dp 表打印出来一行一行核对。比如统计路径数用一个 3×4 的网格手算结果应该是一个类似杨辉三角的对称结构如果某一行出现不该有的 0那就说明上一行的数据被覆盖了或者边界初始化出了问题。还有一个很容易犯的错在循环里修改了输入数组 grid 的值后面再用时发现数据变了。如果不想额外开 dp 表原地改 grid 是一种空间优化手段但它会让代码的可读性下降而且一旦在同一个函数里做二次操作极容易引入隐性问题。初学者我建议老老实实新开一张表等理解透彻了再考虑原地更新这种“省内存”的骚操作。5.3 边界用例是最后的保险每次提交前我都会跑一组最朴素的边界用例1×1 的网格、1×N 的条状网格、M×1 的条状网格、全障碍网格。这几个用例可以快速暴露一大批初始化问题。例如 1×1 网格答案要么是 1计数题要么是 grid[0][0] 本身最值题如果题目代码里不小心把第一列初始化写错这类用例立刻暴露问题。再比如带障碍物版本的 1×N 网格如果第一行中间有个障碍那终点只要在障碍右侧就应该是 0。这种情况下第一行初始化如果只是逐格赋 1而不做 break 截断就会在网格尺寸很小时依然算出错误结果。6. 几点我的个人实操经验最后不做什么总结了分享几个我实际用下来的习惯。第一拿到 DP 题别急着写最优解。先按“暴力递归 - 记忆化搜索 - 递推 dp 表 - 滚动数组”的顺序走一遍。暴力递归帮助梳理状态和转移记忆化搜索相当于给状态表加缓存递推则把递归栈换成了循环最后滚动数组才是压内存。这一步一步迭代比自己直接背一维模板稳得多。第二画表比画路径管用。我会在草稿纸上画一个和题目等比例的小表格然后在表里手填答案基本填到第三行就能看出规律。很多看起来复杂的题意填表格的过程中会自然清晰。第三矩阵路径的套路值得反复练因为它的变体可以应用到很多真实场景从机器人移动路径规划到棋盘类游戏的最短步数预估再到网格状线路的运费计算核心都是同一套“格子状态 上下汇合”的思路。把这个模型吃透之后再遇到状态压缩、树形 DP 这些进阶题你会发现自己更容易理解它们和基础模型的关联。如果非要给一条最实用的建议那就是做题时永远把边界条件写在代码最前面、单独处理不要嵌到循环里靠分支判断硬凑。这个习惯帮我省掉了大量查错时间也推荐你试试。
