矩阵路径动态规划：从二维DP递推骨架到滚动数组优化-北京尧图网络

说实话矩阵路径这组题我至少刷过三遍每次重刷都能发现新的理解角度。如果说动态规划基础篇是在一维数组上琢磨状态怎么滚那么矩阵路径就是把同样的思想摆到二维网格上逼迫你想清楚当前位置的结果到底由哪些邻居决定。这类题在算法面试里出现频率极高从入门级的不同路径到经常被问到的最小路径和再到加大难度的带障碍物路径计数矩阵中的最长递增路径本质上都共享同一套递推骨架。这篇文章把二维 DP 的核心推导、边界初始化的坑、空间优化的原理以及我实际刷题时总结的调试套路完整摊开适合已经掌握一维动态规划、正准备攻克矩阵类题目的读者。1. 先认识这类题矩阵路径的统一长相与识别方法1.1 一个特征就把矩阵路径题从一堆动态规划里挑出来在刷题平台上只要出现给你一个 m×n 的网格/矩阵从某个起点走到某个终点求路径数或最优路径和这样的描述基本可以立刻把它归入矩阵路径类。这类题有几个稳定标签输入是二维结构、移动方向有明确限制最常见的是只能向右和向下偶尔是四方向、问法集中在多少种走法和最大/最小代价两类。我把做过的几道典型题放在一起对比过它们的差别一眼就能看出来题目类型核心问法状态转移依赖最终答案形式不同路径从左上到右下一共有多少条走法上方格子左方格子dp[m-1][n-1]带障碍的路径计数避开障碍物的前提下有多少条走法上方格子左方格子障碍格清空dp[m-1][n-1]最小路径和从左上到右下经过的最小数字总和min(上方左方) 当前格值dp[m-1][n-1]矩阵中的最长递增路径在矩阵中找一条数值严格递增的最长线路上下左右四个方向中值更大者所有格子出发的最大值当你看到题目有这种二维网格受限制移动计数或最优值的包装就应该条件反射地往二维 DP 方向想。注意只要稍微改一下移动规则或问法题目就会从一个模板衍生出完全不同难度的变体这也是它适合被反复拿来考察的原因。1.2 为什么贪心在这里失灵而动态规划正好对症很多人第一反应是我每次走一步选一条看起来最优的路不就行了比如最小路径和每次都挑数字小的格子走。这个方法在局部也许没问题但根本没有全局视角。我举一个简单的反例一个 2×3 网格第一行是 1, 100, 1第二行是 1, 1, 1。从左上角出发第一步往下走数字 1就比往右走数字 100好但真正的最优路径其实是先往右走到 100 再继续因为后面第一行最后一个是 1第二行的开头也是 1。每一步局部最小并不能保证整条路径最小这是贪心的死穴。动态规划能解决问题关键在两点第一到达每个格子时无论之前怎么走之后的选择只取决于当前格子位置而跟具体路线无关这叫做无后效性第二从起点到某个格子的最优结果可以被反复复用到达它下方和右方的格子时都要用到它这叫做重叠子问题。这些条件在矩阵路径题里天然成立。于是我们用一张 dp 表把从起点到每个格子的结果都存下来一步一个脚印推进到终点。2. 经典入门不同路径的完整推导与代码落实2.1 状态定义与转移方程是怎么一步步问出来的不同路径这道题描述特别干净一个机器人在 m×n 网格的左上角每次只能向右或向下移动一步问到达右下角有多少条不同路径。拿到它我先问自己三个问题我从哪个状态开始到达一个格子前最后一步能从哪里来要表达到达某个格子的路径数dp[i][j] 应该是什么第一个问题很容易回答我只关心从起点走到某个格子的路径数所以设 dp[i][j] 表示从起点到达坐标为 (i, j) 的格子的不同路径数。第二个问题更关键。机器人每次只能向右或向下那么能直接走到 (i, j) 的格子只有两个它上方的 (i-1, j) 和左方的 (i, j-1)。也就是说到达 (i, j) 的所有路径要么先走到上方再往下跨一步要么先走到左方再往右跨一步不可能有其他来源。于是转移方程就自然浮出来了dp[i][j] dp[i-1][j] dp[i][j-1]。加法的含义是来自上方和来自左方是两种完全不同的走法数量直接相加。这个推导过程不是背公式而是回到最后一步从哪来这个朴素问题上每次做题都这么问自己一遍状态转移就不会写错。2.2 边界初始化第一行第一列为什么填 1转移方程里出现了 dp[i-1][j] 和 dp[i][j-1]但 i0 或 j0 时下标会变成负数这就是边界格子的由来。第一行i0的格子机器人在最顶部只能一路向右走所以到达其中任意一个格子的路径数都是 1第一列同理只能一路向下路径数也都是 1。只有 dp[0][0] 需要单独想一下它表示从起点到起点不动也是一种方案所以也是 1。我见过很多初学者在初始化时写dp [[1] * n for _ in range(m)]把所有格子都先填成 1再在双层循环里更新内部格子。这么做对纯不同路径没问题但会埋下一个隐患一旦后面的题加了障碍物这种全 1 初始化的写法就会出大问题。所以我更建议一开始就养成习惯先把 dp 表用 0 填满再单独处理第一行第一列明确表达哪些地方是真正的起点边界。基础版本代码可以这样写def uniquePaths(m: int, n: int) - int: 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]这里双层循环从 (1,1) 开始是因为第一行和第一列已经初始化过了不需要再套用转移方程。2.3 公式验证小技巧组合数算出的答案应该一致这道题除了 DP还有一个数学解总共需要走 (m-1) 次向下和 (n-1) 次向右合计 (mn-2) 步问题等价于从这么多步中选出哪 (m-1) 步是向下走因此答案是组合数 C(mn-2, m-1)。这个公式最大的价值不是替代 DP而是用来验证你的递推代码有没有写错。我实测过一张 3×7 的网格dp 表单步推导出来的结果是 28组合数 C(8, 2) 算出来也是 28。我在学习阶段每写完一种写法都会再用另一个思路核对一遍只要两个结果对不上肯定有一边出了问题。面试时如果被追问还有没有别的解法能甩出这个组合数思路也能证明你不是只背了一个模板。3. 坑点最多的变体带障碍物的路径计数3.1 障碍物对 dp 表的影响范围不同路径 II在上一题基础上加了一个条件网格里某些位置有障碍物机器人不能走到这些格子上。核心思路不变但转移方程的写法要加一个判断如果 (i, j) 本身是障碍物那么 dp[i][j] 直接等于 0因为无论从哪个方向都不可能站在这个格子上如果不是障碍物才沿用 dp[i-1][j] dp[i][j-1]。这里要特别注意一个认知误区障碍物不只影响自己所在的格子还会切断后续某些格子的唯一来路。比如第一行出现一个障碍物后它右边的所有格子都不可能到达了因为机器人不能跳过障碍物也不能向下再向上绕回第一行。所以千万不要以为只要在循环内部判断障碍物就够了边界行和边界列的处理方式完全不同。3.2 break 式初始化的直觉来源第一行第一列在带障碍场景下就不能简单全填 1 了。以第一行为例从起点一路向右如果途中碰到一个障碍物那么从这个障碍物开始右边每一个格子都没有任何路径能到达。正确做法是从头开始遍历第一行遇到障碍物就停止循环把当前格和后续格子都保持在 0。我最早写这道题时就栽在这里。我图省事先判断obstacleGrid[0][j] 1时把 dp[0][j] 设为 0否则设为 1结果第一行遇到障碍物后它右边的格子全被错误地赋成 1。后来我用一个具体的 3×3 带障碍用例去推演底表才意识到障碍物应该像一堵墙直接把这一行的路径截断代码里用break比用continue更符合实际含义。def uniquePathsWithObstacles(obstacleGrid: List[List[int]]) - int: m, n len(obstacleGrid), len(obstacleGrid[0]) dp [[0] * n for _ in range(m)] for j in range(n): if obstacleGrid[0][j] 1: break dp[0][j] 1 for i in range(m): if obstacleGrid[i][0] 1: break dp[i][0] 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]3.3 起点和终点是障碍物这两个特殊 case带障碍物版本还有两个特别容易忽略的边界情况。第一个是起点本身是障碍物这时机器人根本站不上出发点答案直接是 0。第二个是终点本身是障碍物同理也是 0。用上面的代码处理这两个场景是安全的起点有障碍时两条初始化循环第一格就会 breakdp[0][0] 保持 0最后返回 0终点有障碍时循环到终点会把它设为 0结果自然为 0。我建议每次写完这类题都手动跑一遍这两个极端输入obstacleGrid [[1]]和obstacleGrid [[0, 0], [0, 1]]。前一个验证起点障碍后一个验证终点障碍。这种习惯能帮你在大批量刷题时减少低级失误也方便在面试中主动跟面试官确认边界条件让对方觉得你想得足够细。4. 从计数到最值最小路径和与滚动数组的空间优化4.1 一个 min 的变化整个题目的思路升级最小路径和是矩阵路径从计数类转向最值类的典型代表。题目给一个网格每个格子里是数字从左上到右下找一条路径使得经过的数字总和最小。状态定义依然清晰dp[i][j] 表示从左上角走到 (i, j) 时的最小累加和。转移方程从加法变成了取小值dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。为什么是 min因为到达 (i, j) 的倒数第二步要么来自上方要么来自左方为了让到达 (i, j) 的路径和最小自然要选择到达上方格子和到达左方格子两者中更小的那个再叠加当前格子的值。第一行和第一列的初始化和上一题不同不能填 1 或 0而要做前缀和累加第一行的 dp[0][j] dp[0][j-1] grid[0][j]因为这条路径只有一条可选路线经过的所有格子数字必须加进来。第一列同理。写代码时我会先单独把这两条边界算好再进入主体循环这样逻辑上非常清晰def minPathSum(grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] for j in range(1, n): dp[0][j] dp[0][j - 1] grid[0][j] for i in range(1, m): dp[i][0] dp[i - 1][0] grid[i][0] 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.2 滚动数组为什么能够成立完整 dp 表需要 O(m×n) 空间但注意转移方程只依赖上一行和当前行左边这两个位置所有更早的数据其实已经没用了。于是可以把二维 dp 压缩成一个长度为 n 的一维数组反复滚动更新这就是滚动数组。我用最小路径和来说明它的运行逻辑。初始化时一维数组 dp 先存第一行的前缀和比如 dp[j] 表示从左上到第一行第 j 列的最小路径和。进入第二行循环后处理第 j 列更新前dp[j] 保存的是上一行同一列的结果也就是从上往下走到当前格子的候选值而 dp[j-1] 此时已经被更新成当前行第 j-1 列的结果也就是从左往右走到当前格子的候选值。两者取 min 再加上 grid[i][j]恰好就是这一格的最优值。这步理解透了代码写法才有底气def minPathSumRolling(grid: List[List[int]]) - int: 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] min(dp[j], dp[j - 1]) grid[i][j] return dp[-1]很多人在这一步卡壳是因为没有意识到同一个 dp[j] 在一轮循环前后代表两个不同行的结果。我把这个点想清楚之后滚动数组在我眼里就像一个滑动窗口窗口里永远只保留当前行完整结果上一行数据用完即弃。两种实现的空间对比非常直观实现方式时间复杂度空间复杂度适用场景完整二维 dp 表O(m×n)O(m×n)思路直观便于讲解滚动一维数组O(m×n)O(n)空间要求高面试加分4.3 加餐要还原具体路径时怎么记录决策有些面试官会追加一句把这条最小路径走法打印出来。dp 表本身只给了最优值没有保存选择过程这时候需要额外开一个 parent 数组记录每个格子到底是从上方还是左方来的。可以约定 parent[i][j] up 表示从上方转移left 表示从左方转移。填充 dp 表的同时填 parent 表最后从终点倒着回溯到起点把路径反过来输出即可。空间优化成滚动数组之后就无法还原路径了因为历史行已经被覆盖。所以如果题目只是问路径和最小是多少用滚动数组如果还要打印完整路径老老实实保留完整 dp 表和一个方向数组。这是我自己的一个取舍习惯先想清楚题目要求的是值还是路径再决定要不要做空间优化而不是无脑上滚动数组。5. 走出标准框架四方向移动的记忆化搜索5.1 当移动方向不受限迭代递推为什么行不通矩阵路径不一定都限定只能向右向下。矩阵中的最长递增路径这道题允许从任意格子出发向上下左右四个方向移动但下一个格子必须比当前格子数值更大。这时你会发现之前的迭代递推思路很难套用因为一个格子的最长路径可能依赖下方、左方、上方、右方任意一个数值更大且尚未计算的格子也就是说依赖方向是四面八方的而不仅限于左上方向。如果用传统双层循环从 (0,0) 按行扫描会遇到一个尴尬局面计算 dp[i][j] 时它依赖的某些邻居比如右边的格子可能还没有被计算出来。就算你尝试调整遍历顺序也无法保证所有格子先于依赖它的格子被处理因为依赖方向完全由数字大小决定并没有固定规律。这不是说不能用 DP 思想而是说单纯的迭代填表方式不够自然。5.2 记忆化搜索的模板与正确性正确姿势是深度优先搜索配合记忆化这份代码本质上是递归版的动态规划。定义 dfs(i, j) 表示从 (i, j) 出发能形成的最长递增路径长度。它的递归过程是检查上下左右四个邻居如果邻居的值比当前格子大就以邻居为起点继续递归最终取所有可行方向中最大的一个再加 1 作为当前格子的路径长度。为了防止重复计算用一个 memo 数组缓存每个格子已经算好的结果遇到已经计算过的格子直接返回。def longestIncreasingPath(matrix: List[List[int]]) - int: if not matrix or not matrix[0]: return 0 m, n len(matrix), len(matrix[0]) memo [[0] * n for _ in range(m)] directions [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(i, j): if memo[i][j] ! 0: return memo[i][j] best 1 for di, dj in directions: ni, nj i di, j dj if 0 ni m and 0 nj n and matrix[ni][nj] matrix[i][j]: best max(best, 1 dfs(ni, nj)) memo[i][j] best return best return max(dfs(i, j) for i in range(m) for j in range(n))这份代码不用额外的 visited 数组因为移动条件是严格递增数字只会越来越大天然不可能走回已经访问过的位置不会形成环。memo 初始值为 0 也有讲究只要 memo[i][j] 不是 0就说明这个格子的结果已经计算完毕可以直接复用。这个写法我第一次看时觉得绕后来想通了递归是从一个点向外扩散迭代是从起点逐步逼近终点两者只是执行方向不同底层共享同一个用子问题结果组装父问题结果的 DP 内核。5.3 动态规划和记忆化搜索怎么选我的选择标准很简单当依赖方向固定比如始终依赖左方和上方优先用迭代 DP代码直观且不会有递归栈溢出风险当依赖方向不固定或依赖关系复杂比如四方向扩散、依赖条件按值的相对大小决定记忆化搜索往往更容易实现因为递归天然擅长处理这种走一步看一步的逻辑。面试里如果碰到这类题我一般会先说清楚暴力递归能做然后用备忘录去重最后点明它和动态规划是同一套思想。这样既展示了对复杂度的敏感也不会在递归和递推之间显得只会一种。另外一个工程层面的小提醒递归深度在极限情况下可能等于格子总数如果矩阵特别大要留意语言默认栈深度的上限。6. 实操避坑清单我把矩阵路径题里的常见错误汇总了一遍6.1 每道题开工前先回答的三个问题刷到一道矩阵路径题我拿到题面后不会立刻写代码而是先强制自己回答三个问题dp[i][j] 到底表示什么到达当前格子的候选来源有哪些第一行和第一列的初始值如何计算这三个问题分别对应状态定义、转移方程、边界条件是这类题的全部骨架。其中第一个问题最容易出错。比如有些题要求最大正方形面积dp[i][j] 的含义就变成了以 (i, j) 为右下角的最大正方形边长转移依赖则同时涉及上方、左方和左上三个邻居不再是简单的路径计数。所以不要条件反射式地把所有题都套进同一个状态定义先花三十秒想清楚每个格子的语义后面全部顺理成章。我还有一个习惯正式写代码前先画一个 3×3 或 4×4 的小网格手动把 dp 表前两行算出来。半小时的纸上推演能省下两小时的调试时间。刷题平台的测试用例毕竟有限自己手推一遍才能真正建立对转移过程的直觉。6.2 值得收藏的边界用例我整理了一批每次都会跑一遍的边界用例这里分享给读者用例输入特征预期结果容易踩的坑单格m1, n1该格数字或 1忘记处理 dp[0][0]单行m1, n1一路向右累加第二层循环越界单列m1, n1一路向下累加第一行初始化错误传播全障碍起点或终点是 10break 条件写错全零矩阵所有格子为 0最小路径和为 0边界累加逻辑有误递增路径极端值单元素矩阵1递归边界忘记返回这些用例的价值在于快速暴露两类问题数组越界和初始化错误。数组越界往往发生在 m1 或 n1 时因为双层循环里访问 dp[i-1] 或 dp[j-1] 会用到不存在的行或列初始化错误则藏得更深不容易一眼看出来只能靠正确用例去验证。6.3 面试时怎么把思路讲清楚又不啰嗦如果现场面试遇到矩阵路径题我会按这套顺序表达先把暴力做法说出来递归枚举所有路径指数级复杂度然后指出路径之间有大量重叠子问题接着抛出自上而下的记忆化搜索版本最后过渡到自下而上的迭代动态规划强调状态定义、边界条件和转移方程。这样既展示了完整的思维过程又不会显得只是在背模板。讲转移方程时最好用手指在虚拟的网格上画一画当前格子的答案来自上方和左方或者用一个小例子把第一行的边界值念一遍。面试官通常更关心你有没有真正理解为什么这个转移成立而不是你背了多少个题解。把最后一步从哪来这句话反复说清楚基本就能把一道矩阵路径题讲透。最后再分享一个我个人的刷题习惯每做完一道矩阵路径题我都会顺手把完整二维数组写法改成滚动数组写法再跑一遍同样的测试数据。这个动作看起来多花了十分钟实际上能同时巩固空间压缩原理和边界初始化两块知识。刷完一个专题后我对动态规划的认识也会上一位。实际动手时你会发现矩阵路径的每一道变体都是同一个递推灵魂换了一身衣服认清了它的本质之后无论题目怎么包装都不会慌。

矩阵路径动态规划：从二维DP递推骨架到滚动数组优化

相关推荐

51单片机矩阵键盘与数码管动态显示：完整电路、代码与调试指南

全球柯本气候区划SHP数据：GIS空间分析的气候语义锚点

OP-TEE最小测试工程实战：TA/CA通信与QEMU部署避坑指南

更多资讯

随机化快排实战：防退化、稳性能、抗恶意输入

圆形物体检测实战：霍夫变换与分割模型选型及参数调优指南

从目录结构读懂自动化编排框架 OpenClaw 的架构设计与扩展机制

如何在Java中打印pdf静默打印和打印对话框选择

HTTP重定向深度解析：状态码语义、服务端实现与常见陷阱

9款AI论文工具实测：专科生开题报告从空白到初稿的完整流程

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？