矩阵路径问题在动态规划里的地位有点像排序在算法里的地位——几乎是必练的入门题。它表面上就一个网格、一个起点、一个终点似乎不难但真上手写代码的时候边界条件、初始化、状态转移方程里的加号和取min处处都能让人翻车。这篇我们就把动态规划Ⅱ矩阵路径这件事彻底聊透从最经典的计数路径开始到带障碍物、带权值的变种再到滚动数组的空间优化最后整理成一套可以拿来就用的解题模板。适合刚学到动态规划这个章节、或者已经能写简单DP但总是卡在边界条件上的读者。1. 矩阵路径问题到底在考什么1.1 从一个网格的故事说起先描述一类你肯定见过的题目有一个 m 行 n 列的网格机器人从左上角出发每次只能向右走一步或者向下走一步要走到右下角。问题通常是两个问法——第一一共有多少条不同的路径第二如果每个格子上有一个代价数字走一条路径的总代价最小是多少。这类问题看起来像搜索但指数级的路径数量根本搜不完所以需要动态规划。它为什么能DP关键在于到达某个格子这件事只依赖它上方和左方的格子。机器人不能回头不能斜着走那么所有到达 (i, j) 的路径最后一步只有两种可能要么从 (i-1, j) 往下走要么从 (i, j-1) 往右走。这正好满足动态规划的重叠子问题结构大问题是到达终点子问题是到达某个中间格。生活化的类比就是你要从小区门口走到单元楼下只能往东走和往南走。到达十字路口 A要么从北边的路口走下来要么从西边的路口走过来。只要把到达每个路口的可能路线数算清楚最后答案自然就出来了。这也是矩阵路径问题最友好的地方不需要抽象建模状态天然就是坐标。1.2 动态规划解题的四个固定动作与其背题不如建立一套稳定的解题顺序。矩阵路径类DP我建议一律走四步定义状态、写转移方程、初始化、确定遍历顺序。第一步定义状态一般写成 dp[i][j]含义是从起点到达 (i, j) 的某种结果可能是路径数量也可能是最小代价。第二步写转移方程根据最后一步推导计数型用加法最值型用 min 或 max。第三步初始化通常要处理第一行、第一列和起点。第四步确定遍历顺序矩阵路径基本都是从上到下、从左到右因为计算 dp[i][j] 需要先知道 dp[i-1][j] 和 dp[i][j-1]。这四个动作里初学者最忽视的是初始化。很多人把数组一建所有值默认0然后就在转移方程里找答案结果边界值全是0答案怎么算都不对。反过来有人图省事把整个数组初始化为1遇到带障碍物的题目又全错了。初始化不是走过场它是在回答最靠边的格子到底怎么到达这个问题。2. 两道经典矩阵路径题的完整拆解2.1 不同路径计数型DP怎么推先看最经典的题目没有障碍物m x n 网格求不同路径总数。我习惯用 3x3 来手推。起点处路径数为1因为没有别的路可走。第一行的格子呢因为只能向右走从起点到 (0, j) 只有一条路径——一直向右所以 dp[0][j] 1。第一列同理只能一直向下dp[i][0] 1。至于内部的格子比如 (1,1)它可以从 (0,1) 下来也可以从 (1,0) 过来两边到达方式加起来就是 dp[1][1] dp[0][1] dp[1][0] 2。把这个过程推广到整个矩阵转移方程就是dp[i][j] dp[i-1][j] dp[i][j-1]写成代码最直观的二维版本是这样def uniquePaths(m: int, n: int) - int: 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 数组初始化为 1因为第一行和第一列的答案恰好都是1这样省去了手工初始化边界。但这招只在无障碍物时成立很多读者学到这里很爽后面遇到加强版立刻就不适应了。记住这个初始化为1的技巧本质上是把你应该显式思考的边界条件藏起来了能理解藏的是什么才算真正掌握。2.2 最小路径和最值型DP怎么推另一道必练题是带权值网格的最小路径和。每个格子有一个非负数字要求从左上到右下沿途经过的数字之和最小。转移方程从加法变成min 加当前值dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])为什么用 min因为到达同一格子的路径有很多条每一条对应一个历史代价我们只想知道最小的那个所以保留上方路径和左方路径里更小的值再加上当前格子的代价。二维写法def minPathSum(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] grid[i][j] min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]对比前面不同路径的代码你会发现最大差异就在初始化。不同路径第一行第一列全为1最小路径和却要逐个累加因为到达每个边界格子的代价不是恒定的而是沿途格子累出的和。如果照抄上一题的初始化答案会少算很多。另外注意题目说格子权值非负所以 min 的选择才安全。如果出现负数单纯贪心在当前步取 min 就可能出问题但那是另一类题矩阵路径DP的经典版本基本默认非负。3. 空间优化从二维DP到一维滚动数组3.1 为什么二维DP数组不是终点很多读者能顺利写出二维 DP心想 O(m*n) 的空间也没多大错。确实在本地跑测试1000x1000 的网格也就一百万个格子一个 int 数组才几 MB问题不大。但在在线评测系统里出题人常常会把 m、n 都拉到 10000 甚至更大这时候二维数组就需要 1 亿个元素内存直接爆掉而且矩阵越大缓存命中率也跟着下降。更重要的是矩阵路径 DP 的依赖关系给了我们一个天然优化点每个新格子的值只来自上一行和当前行左侧跟更早的行完全没有关系。既然旧行用完不再需要那就不必保存整个表格只需保留当前行的滚动数组。这个优化能让空间从 O(m*n) 降到 O(n)在很多大矩阵场景下是决定生死的关键。这就像记账你只需要记住昨天账目和今天已经记了一部分的账目前天以前的账目翻篇就不再参与计算了。没必要把一辈子的流水都摆在桌上。3.2 滚动数组的推导过程和细节先说结论以最小路径和为例。二维转移方程是dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])如果我们用一维数组 dp[j] 表示当前行第 j 列从左到右更新到某个时刻的状态那么在处理第 i 行时还没更新前的 dp[j]存的其实是上一行第 j 列的值对应 dp[i-1][j]已经更新完的 dp[j-1]是当前行第 j-1 列的新值对应 dp[i][j-1]。于是转移方程变成dp[j] grid[i][j] min(dp[j], dp[j-1])一维代码def minPathSum(grid): 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] min(dp[j], dp[j-1]) grid[i][j] return dp[n-1]这段代码里最容易被忽略的是 dp[0] 的处理。dp[0] 永远代表当前行第 0 列它只能从上方来所以在每一行开始时要累加 grid[i][0]。如果你把 dp[0] 也丢进 min 逻辑里就会把左边来的值当成一种可能但第 0 列根本没有左边的格子结果必然错。再回到不同路径的一维版本def uniquePaths(m: int, n: int) - int: dp [0] * n dp[0] 1 for i in range(m): for j in range(1, n): dp[j] dp[j] dp[j-1] return dp[n-1]dp[j] 更新前是上一行的值dp[j-1] 是当前行刚算出的左边值两者相加就是到达当前格子的路径总数。这个写法简洁到让人想背下来但我必须提醒内层循环一定要从左往右。如果反过来从右往左遍历dp[j-1] 还没被当前行更新用的还是上一行的旧值相当于把一条路重复算了两次结果会比正确答案大。这是滚动数组最经典的翻车点。4. 边界条件与障碍物的坑4.1 障碍物处理从可达到跳过加了障碍物之后很多背模板的代码瞬间失效。经典题目是网格里有值为1的格子不能走求路径总数。核心变化只有一个——不可达的格子它的路径数必须是0。状态转移方程本身不变仍然是左加右但落在障碍物上的格子不能参与计算也不能向后续格子传递路径数。用二维思维写就是这样def uniquePathsWithObstacles(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(m): for j in range(n): if obstacleGrid[i][j] 1: dp[i][j] 0 elif i 0 and j 0: continue elif i 0: dp[i][j] dp[i][j-1] elif j 0: dp[i][j] dp[i-1][j] else: dp[i][j] dp[i-1][j] dp[i][j-1] return dp[m-1][n-1]值得留意的是第一行和第一列的处理。之前无障碍时第一行全为1现在不行如果第一行某个格子是障碍它自身为0它右边的所有格子都无法从左边的路径延续过来所以也都应该是0。第一列同理如果中间某个格子是障碍它下面所有格子都无法从上方延续过来。换句话说障碍物会截断整条边界链。用滚动数组写更紧凑但要注意执行顺序def uniquePathsWithObstacles(obstacleGrid): m, n len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] 1: return 0 dp [0] * n dp[0] 1 for i in range(m): for j in range(n): if obstacleGrid[i][j] 1: dp[j] 0 elif j 0: dp[j] dp[j-1] return dp[n-1]这里 j 0 且无障碍时 dp[0] 不做任何操作它保留的是上一行同一列的值也就是从上方下来的路径数。如果上方已经被障碍物截断dp[0] 会早就是0了自然能正确传导。这个写法优雅但初学者容易理解不了建议先在纸上画一个带障碍的网格逐行模拟一遍 dp 数组的变化很快就能吃透。4.2 初始化时的经典翻车现场我在实际写题和帮人review代码的过程中见过最多的错误都集中在初始化这里整理成一份翻车清单。第一个错误把整个 dp 数组初始化成1然后直接套无障碍模板。一旦网格里出现障碍物障碍物之后的边界格子仍然残留1路径数就被高估了。正确的做法是让边界值由是否可达动态决定而不是预先写死。第二个错误判断障碍物时顺序写反。先判断了 j 0 再做状态转移却发现当前格本身就是障碍于是它仍然把左边、上边的值加了过来障碍物形同虚设。必须先处理障碍物把 dp[j] 置成0再对非障碍格做转移。第三个错误起点或终点障碍物没有特判。起点是障碍物意味着根本没有路径直接返回0终点是障碍物也同理但很多代码因为初始化把 dp[0][0] 强行设为1终点虽然标了障碍却被转移方程赋了一个非零值最后错误输出1。这两个特判属于白送分千万不要丢。第四个错误最小路径和遇到障碍物时用 0 代替路径。求最小和时障碍物不能走但用0会让它变成一条免费通道应该在障碍物位置放一个极大值比如 float(inf)这样 min 计算时永远不会选中它。5. 变种题与扩展思路5.1 路径输出、差异值、带权路径会做经典题之后很多题目会在状态内容上做文章。比如要求输出任意一条最短路径而不是只求路径数。怎么做在二维 DP 更新的同时额外维护一个 directions 表记录每个格子是从上方还是左方转移过来的。最后从终点出发沿着 directions 表一路回溯到起点反转一下顺序就能得到完整路径。再比如求最大路径和只需要把 min 换成 max同时把障碍物处理成负无穷大思路完全一致。还有求路径上最大值与最小值之差最小的路径这类差值问题通常不会直接出现在状态里而是需要调整状态定义把 min 和 max 同时记录在状态里或者用二分答案配合 DP 判断可行性。这些变种的核心还是那张表只是表里存的东西变多了。还有一种常见变化是把走到终点改成必须经过某个特定点。这听起来很难其实拆成两段来做就行先求起点到特定点的结果再求特定点到终点的结果两者组合。因为这些路径是向右向下单向流动的特定点一旦确定前后两段互不干扰这是矩阵路径类题目里比较巧妙的套路。5.2 不只是向右向下更大范围的状态设计如果题目允许上下左右移动但每个格子只能访问一次这就不是简单 DP 问题了。原因是状态除了坐标之外还要记录哪些格子已经被访问过压缩状态本质上变成状压 DP 或搜索不再符合无后效性的假设。判断一个题能不能用矩阵路径 DP先看移动方向是否被限制在右和下这是一个很实用的经验。还有一类升级题是引入生命值之类的维度。最典型的例子从左上到右下途中有房间会扣血或加血要求任意时刻生命值至少为1求初始最少要带多少血。这个题如果从起点正着做当前血量会影响后续决策直接二维 DP 不够用。正确的做法是反过来定义状态dp[i][j] 表示从 (i, j) 出发到终点所需的最少初始生命值然后从右下角向左上角推导。这种反向定义状态的转折经常是矩阵路径题从入门到进阶的分水岭。遇到题时如果正着推不顺畅先试试把目标和起点互换往往会出现转机。6. 常见问题与排查技巧实录6.1 题做错时的三种典型症状症状一答案偏大。常见原因有两个一是初始化把整张表填了1导致不可达的边界格子也被算了路径二是滚动数组内层循环方向写反了左侧新值被重复使用。排查时先把 m、n 改成 2、3 这种极小规模手工算出预期答案再对比代码每一步的 dp 表很容易定位。症状二答案偏小。最典型的是最小路径和忘了加当前格子权值或者边界格子初始化时漏了累加。如果是最优型 DP检查一下 dp[i][j] 的公式里有没有把 grid[i][j] 加回去。另一种情况是障碍物处理后某个应该可达的格子被残留的0挡住比如滚动数组里 dp[j] 曾经因为障碍物被置0但同一行后面没有正确恢复导致后续格子全部为0。症状三内存溢出或运行时间爆炸。这通常不是算法逻辑错而是用了二维数组但没做滚动数组优化或者 m、n 很大但代码里用了递归搜索。矩阵路径 DP 的复杂度应该是 O(m*n) 时间、O(min(m,n)) 空间如果超出这个量级先检查空间优化是不是漏了。为了方便对照我把常见问题整理成一个速查表症状可能原因检查方法结果偏大障碍物边界没有置0滚动数组方向反打印每行dp手工推3x3结果偏小最优型漏加当前格值障碍物格用了0核对转移方程看是否少了一个加号障碍物失效先算转移再判断障碍顺序反了在障碍物处理前后各打印一行起点/终点障碍缺少特判单独写 if 直接返回内存爆掉没有滚动数组优化改用一维 dp同时保留二维版对拍6.2 调试DP代码的实用方法我在实际学习时最受益的一个习惯拿到 DP 题先在纸上画 3x3 的表格手写一遍状态值。这一步看着慢实际比在代码里反复打印快得多。比如无障碍 3x3 的不同路径手写结果是第一行全1、第一列全1、中间是2、再到右下是6。如果代码输出不是6你立刻知道问题在初始化还是转移。第二个方法是给滚动数组加临时打印。每处理完一行print 当前的 dp 数组。小规模下你能直观看到上一行状态是如何被当前行覆盖的尤其能暴露 dp[0] 是否正确更新。看到 dp[0] 一直保持1你就明白第一列路径数确实恒为1看到最小路径和的 dp[0] 在逐行累加你也就理解边界列不能照搬计数型模板。第三个方法是对拍。写一个简单的 DFS 暴力搜索在小网格比如 3x4中枚举所有路径得到标准答案再和 DP 答案比较。对拍代码不用考虑效率只求正确它能帮你确认 DP 公式在数学上没问题。等小规模对拍全部通过再把 m、n 提高测滚动数组的边界情况。最后分享一个小建议新手阶段不要一上来就写滚动数组。先写二维 dp确认逻辑正确再手动把二维下标全部替换成一维带着dp[j] 是被覆盖的旧值这个意识去改。我见过太多人直接写一维结果折腾一小时找不出错但让他先写二维再翻译五分钟就改了回来。这不是智商问题而是二维下标能保留上一行 vs 当前行的直观视觉一维版本把这种区分隐藏了。等一维写熟了再追求一步到位也不迟。