前段时间朋友问我LeetCode 62 的“不同路径”做完之后再刷 63 的“不同路径 II”为什么明明只多了一个障碍物代码却总在最简单的边界条件上报错。这问题太典型了。63 题是动态规划的入门进阶题在一个 m x n 网格里机器人从左上角走到右下角每次只能向下或向右网格中用 1 表示障碍物、0 表示空地让你统计不同的路径条数。表面上看只是给 62 加了个限制但障碍物一出现组合数学解法直接失效DP 初始化、状态转移、空间优化这些基本功全被暴露出来。这篇文章不是把答案抄一遍而是把这道题的完整拆解、代码演化、面试扩展讲清楚适合准备算法面试、正在啃动态规划专题、或者想搞明白路径计数问题的读者。1. 不同路径 II 的题意与解题方向选择1.1 题目到底在考什么先对齐题目细节。输入是一个二维数组obstacleGridobstacleGrid[i][j] 0表示空地obstacleGrid[i][j] 1表示障碍物。机器人从(0, 0)出发每次只能向右走一格或者向下走一格目标是到达(m - 1, n - 1)。障碍物所在的格子不能进入问总共有多少条不同的合法路径。原题约束1 m, n 100网格规模不大最暴力的深搜也勉强能跑但一定会超时因为路径数是指数级的。这道题真正考察的点有两个第一能不能把“计数”转化为“状态累加”第二能不能处理路径上的局部限制也就是障碍物。题目里隐藏的细节也不少。比如起点或者终点本身就是障碍物答案直接是 0第一行或者第一列一旦出现障碍物它后面的格子都不可能到达中间某个格子被障碍物挡住它就不再参与路径计数但周围格子的状态不能跟着乱。这些细节看起来简单实际写代码时非常容易漏后面我会专门讲。1.2 为什么先排除纯组合数学很多刷题顺序是 62 - 6362 题用组合数特别爽总步数是m n - 2其中必须选m - 1步向下所以路径总数是C(m n - 2, m - 1)。到了 63 题只要网格里有一个障碍物这个公式就不能直接用了。你可以尝试“总路径数减掉经过障碍物的路径数”但问题马上复杂起来如果路径同时经过两个障碍物这一减就减重复了需要容斥原理。障碍物一多组合数学的公式推导会变成一场噩梦别说面试时间给你半个小时都不一定推对。我不是说组合数学不能做。确实有办法把障碍物按坐标排序然后用扫描线或者分段计数的方式来处理障碍物数量为 k 时复杂度可以做到O(k^2)左右。但这样做代码量陡增而且容斥的去重逻辑很容易在某个边界上翻车。面试不是数学竞赛面试官更想看到你把问题拆成局部状态用动态规划稳稳地推出来。所以这道题的正解是 DP。1.3 “当前格子”视角的 DP 直觉动态规划的核心是状态定义。对路径计数问题最自然的状态就是dp[i][j]表示从左上角(0, 0)走到(i, j)一共有多少条合法路径。为什么这个定义好用因为机器人只能向下和向右移动那它到达(i, j)之前上一步只可能来自两个地方上方的(i - 1, j)或者左侧的(i, j - 1)。所以到达当前格子的路径数就是到达上方格子的路径数加上到达左侧格子的路径数。如果当前格子本身是障碍物那就没有任何路径能进入它直接记 0这个 0 还会影响它后面格子的计算。可以打个比方把每一条路径想象成一条支流(i, j)这个点是两条支流的汇合处。上游水量等于正上方和正左方两支水量的和如果这个点有拦坝也就是障碍物那这个点的水量就是 0它不会再给下游供水。这个比喻用来理解转移方程非常直观。1.4 边界与初始化第一行第一列是重点按刚才的转移方程i 0的行没有“上方”j 0的列没有“左侧”所以边界必须单独处理。先说第一行。第一行只能从左边一路走过来dp[0][0]如果不是障碍物就初始化为 1然后从左往右走。如果(0, j)是空地dp[0][j] dp[0][j - 1]如果(0, j)是障碍物dp[0][j] 0。这里的关键是第一行一旦出现第一个障碍物它右边的所有格子都不可达所以后面会一路继承 0。第一列同理。只能从上边走下来如果(i, 0)是空地dp[i][0] dp[i - 1][0]如果遇到障碍物置 0后面的格子也全都不可达。很多初学者会先“把第一行全部初始化为 1遇到障碍物再改”这是错误写法。因为障碍物之前确实是 1但障碍物后面的格子不应该是 1。这种“前缀连续性”必须通过继承前一个格子的值来实现不能先统一填 1 再覆盖。2. 从二维 DP 到滚动数组的空间优化2.1 二维 DP先把正确性跑通第一种写法直接用二维数组逻辑最清晰适合先让思路落地。from typing import List class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: if not obstacleGrid or not obstacleGrid[0]: return 0 m, n len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] 1 or obstacleGrid[m - 1][n - 1] 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: dp[i][j] 1 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]我特意在开始处加了一个空网格防御判断。力扣题目保证网格非空但真实项目里入参可能不规范这种防御写上去不会扣分反而显得有工程意识。提前判断起点和终点是不是障碍物也很有必要。起点是障碍物时机器人第一步就迈不出去终点是障碍物时结果一定为 0。提前返回能让后面的逻辑简单不少也避免某些实现把起点障碍物错误地“绕过”。这里的写法是双层循环内统一处理边界好处是逻辑集中不用单独写两段初始化第一行第一列的代码。当i 0时dp[i][j]只继承左边的值当j 0时只继承上面的值效果和先初始化边界再递推完全一致。2.2 滚动数组为什么从左往右更新二维 DP 的时间复杂度是O(m * n)空间复杂度也是O(m * n)。对于 100 乘 100 的网格完全没问题但如果面试官问能不能把空间压下来你就需要滚动数组。观察转移方程dp[i][j]只依赖上一行的dp[i-1][j]和当前行左侧的dp[i][j-1]。也就是说我们不需要保留整个二维表格只需要保留“上一行的结果”一边遍历一边更新当前行。用一个长度为n的一维数组dpdp[j]在进入当前行之前存的是上一行第j列的值。从左到右遍历当前行时dp[j - 1]已经被更新成当前行左侧的值所以dp[j] dp[j] dp[j - 1]刚好就是“上方 左侧”。from typing import List class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m, n len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] 1 or obstacleGrid[m - 1][n - 1] 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]这里一定要记住内层循环必须从左往右更新。如果从右往左那么dp[j - 1]还是上一行的旧值而不是当前行左侧刚算出的新值结果就会漏掉左侧路径。另外遇到障碍物时必须把dp[j]置 0不能只跳过不处理。因为下一行再遍历到这里时这个 0 会作为“上方路径数”参与计算如果保留旧值等于把绕过障碍物的非法路径也算进去了。如果n特别大、m比较小完全可以交换维度按列方向滚动让空间变成O(min(m, n))。思路一样只是把“向下/向右”的角色互换。面试时提一句“我会选择滚动较短的那一维”会显得更专业。2.3 原地修改数组O(1) 空间但别乱用还有更极端的做法直接在obstacleGrid上原地累加。因为每个格子最多被读两次更新之后不再需要原始值。遇到障碍物就把格子改成 0遇到空地就把格子的值改成“上方加左侧”。from typing import List class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m, n len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] 1 or obstacleGrid[m - 1][n - 1] 1: return 0 obstacleGrid[0][0] 1 for i in range(m): for j in range(n): if i 0 and j 0: continue if obstacleGrid[i][j] 1: obstacleGrid[i][j] 0 else: up obstacleGrid[i - 1][j] if i 0 else 0 left obstacleGrid[i][j - 1] if j 0 else 0 obstacleGrid[i][j] up left return obstacleGrid[m - 1][n - 1]这个代码也能通过空间复杂度是O(1)。但我个人不建议在面试一开始就写这个版本。原因很简单直接修改入参在工程上是个坏习惯外面的调用方可能还拿着这份数据做别的事而且把原始网格和 DP 值混在一起可读性会下降。面试时更好的表达是“我可以先用滚动数组把空间优化到 O(n)如果面试官允许修改入参还可以进一步做到 O(1) 空间。”先展示能力再展示工程判断比上来就炫技稳妥得多。3. 记忆化搜索换个角度看同一模型3.1 反向递归的状态拆解动态规划除了自底向上的递推还有一种自顶向下的写法记忆化搜索。它的思路是从起点出发把问题递归地拆给子状态。定义dfs(i, j)表示从(i, j)出发到终点(m - 1, n - 1)的路径数。那么如果(i, j)越界或者是障碍物返回 0如果(i, j)就是终点返回 1否则dfs(i, j) dfs(i 1, j) dfs(i, j 1)。这个状态定义和dp[i][j]是互为镜像的。递推版本从起点往终点推记忆化版本从当前格往终点问答案但转移依赖都来自“右侧”和“下方”。如果不用缓存直接递归路径数会爆炸式增长因为同一个格子会被反复访问很多次。加上缓存后每个格子只计算一次时间复杂度就回到O(m * n)。3.2 用 lru_cache 实现记忆化搜索Python 写记忆化搜索很方便直接用lru_cache装饰器from functools import lru_cache from typing import List class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m, n len(obstacleGrid), len(obstacleGrid[0]) lru_cache(maxsizeNone) def dfs(i: int, j: int) - int: if i m or j n or obstacleGrid[i][j] 1: return 0 if i m - 1 and j n - 1: return 1 return dfs(i 1, j) dfs(i, j 1) return dfs(0, 0)这段代码非常简洁连起点和终点障碍的特判都不用单独写因为dfs(0, 0)会自动返回 0。lru_cache会把(i, j)作为缓存键同一个坐标只算一次。要注意递归深度。m和n到 100 时最大递归深度接近 200还在 Python 默认限制内如果题目规模变大比如网格长宽到几千递归就可能爆栈需要sys.setrecursionlimit或者直接用递推。我一般会在做这道题时先写递推版本再用记忆化搜索作为“思路补充”面试时两版对比着讲效果很好。3.3 递归与递推怎么选从结果上看两个版本复杂度一样。区别在于递推是迭代没有额外栈开销配合滚动数组还能把空间压到 O(n)记忆化搜索思路更接近暴力递归容易想但缓存是二维的空间基本是 O(m * n)记忆化搜索天然支持“只算需要访问的状态”如果网格特别稀疏可能比完整遍历更快但本题网格是稠密的优势不明显。我个人给刷题朋友的建议是以递推为默认答案以记忆化搜索为备用思路。面试官如果追问“还有没有别的解法”你把记忆化搜索拿出来至少证明你理解了状态之间的依赖关系而不是靠背模板。4. 边界条件与典型案例实测4.1 我反复踩过的五个坑这道题最邪门的地方不在核心递推公式而在那些看似不起眼的边界细节。我自己写题和给别人讲题时下面几个坑出现频率最高。第一个坑起点或终点是障碍物。如果不做特判有些写法会把终点障碍物也参与累加最后返回一个不合法的数字。最安全的做法是开头直接判断见一个返回一个。第二个坑第一行第一列初始化错误。很多人从 62 题带过来的习惯是先给边界填 1再处理障碍物。比如第一行[0, 1, 0]如果先把三个格子都填 1第二个格子是障碍物不改第三个格子会拿到错误的 1。正确的做法是障碍物后面的格子必须继承 0不能有“断路”之后仍然可达。第三个坑行列搞反。m len(obstacleGrid)是行数n len(obstacleGrid[0])是列数。访问时先写行再写列一旦弄反要么越界要么结果完全不对。这种错误在代码里非常隐蔽因为小规模测试时可能碰巧不报错。第四个坑滚动数组遇到障碍物不置 0。只把障碍物那一格跳过下一行累加时这一格残留的旧值就会被当成上方路径数把所有绕路路径都算出来。必须在if obstacleGrid[i][j] 1时立刻dp[j] 0。第五个坑遍历顺序写反。滚动数组从左往右更新是因为要使用左侧已经更新好的当前行值。如果写成从右往左用的是上一行的左侧值路径数会少算一大块。4.2 测试用例速查表刷题不能只靠力扣的示例自己要多准备几组边界用例。下面这张表我用过很多次每次写完代码都先跑一遍再提交。场景输入网格期望结果理由官方示例[[0,0,0],[0,1,0],[0,0,0]]2中间有障碍只能从两侧绕行单格空地[[0]]1起点即终点单格障碍[[1]]0起点就是障碍物单行有障碍[[0,0,1,0]]0终点前被障碍物挡死单列有障碍[[0],[0],[1],[0]]0唯一通路上有障碍物两行三列转折[[0,1,0],[0,0,0]]1只能先下再右再右终点障碍[[0,0],[0,1]]0终点无法进入四行四列无障碍[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]20对照 62 题组合数C(6,3)20这组用例覆盖了单行单列、起点障碍、终点障碍、障碍物挡死路径、无障碍对照等关键分支。我推荐你把它们写成单元测试每次改动代码后一键跑一下比盯着屏幕干找 bug 快得多。4.3 面试官常问的四个变体63 题本身只是起点面试官经常在这个基础上做扩展这些扩展也值得提前准备。第一个变体如果机器人可以上下左右移动问能不能到达终点。这时候路径可能无限多条不能再计数。解法变成 BFS/DFS 连通性判断甚至可以用并查集。核心区别是问题从“计数”变成了“可达性”。第二个变体如果要求最短路径长度。因为机器人每走一步代价相同BFS 可以做到 O(m * n)。如果还是只能向右向下那最短路径长度固定是m n - 2没有优化空间这题就失去了问的意义。第三个变体如果要求输出任意一条具体路径。DP 算出所有dp[i][j]之后从终点往回走终点左边和上方的路径数之和等于终点的值哪边不为 0 就往哪边回溯。这个思路也能顺便验证你对 DP 表是否真正理解。第四个变体如果网格特别大障碍物又很少。滚动数组仍然是 O(m * n)碰到万级以上的网格可能不适用。这时可以考虑基于障碍物坐标的稀疏计数复杂度可以压到 O(k^2)k 是障碍物数量。这已经超出面试常见深度了知道方向即可。5. 动态规划题的系统打法5.1 五步法套用做动态规划题我习惯固定用五个步骤避免看到题目脑子一热就开始写循环。第一步确定 dp 数组含义。本题是dp[i][j]表示从起点到当前格子的路径数。第二步写转移方程。本题是dp[i][j] dp[i - 1][j] dp[i][j - 1]遇到障碍物置 0。第三步初始化。起点是 1边界用继承逻辑。第四步确定遍历顺序。外层逐行、内层逐列从左到右。第五步拿一个小例子手动模拟比如两行两列[[0,0],[0,0]]推出 dp 表dp[0][0] 1dp[0][1] 1dp[1][0] 1dp[1][1] dp[0][1] dp[1][0] 2结果和直觉一致。如果中间有障碍再模拟一遍马上就能发现初始化或者边界处理哪里不对。手动模拟不是浪费时间而是最快暴露错误的方式。5.2 面试讲题话术面试时思路清楚很重要你可以按下面的结构向面试官表达“我定义dp[i][j]为从左上角到(i, j)的路径数。因为机器人只能向下和向右走所以dp[i][j]等于上方格子的路径数加左侧格子的路径数。如果当前格子是障碍物就置 0。第一行和第一列要继承前一个格子的值一旦出现障碍物后面全为 0。这样完整遍历一遍网格最后返回dp[m - 1][n - 1]。时间复杂度 O(m * n)空间可以用滚动数组优化到 O(n)。”这段话短但把状态定义、转移、初始化、复杂度和优化全讲清楚了。面试官接着问变量你再把记忆化搜索和原地修改的版本拿出来基本就能收尾。5.3 同类题目串联刷法刷完 63 题后我建议立刻刷下面几道它们都共享同一个“网格 DP”骨架题目核心区别一句话提示62 不同路径无任何障碍物可以组合数学也可以 DP 入门63 不同路径 II有障碍物障碍物位置单独置 064 最小路径和求最小和不是计数转移方程从加法变成取 min70 爬楼梯一维路径计数先理解一维再上二维120 三角形最小路径和三角形网格自底向上 DP 更顺手LCR 166 珠宝的最高价值网格取最大值和最小路径和思想一致LCP 07 传递信息有向图按步数计数可以按轮次滚动数组把这些题放在一起对比你会发现动态规划的核心不是背模板而是准确回答三个问题状态是什么状态怎么转移边界怎么初始化。这三个问题想清楚63 题和这一整类网格题就都能拿下了。最后分享一个我自己刷题时的习惯拿到这类路径计数问题先别急着写题解模板。找一张白纸把(i, j)格子写出来标出它的上方和左方然后问自己“如果我站在这个格子上上一格可能是哪里”。这道题所有解法包括递推、滚动数组、记忆化搜索都是从这么一句简单的话长出来的。你把这个思考过程练成肌肉记忆以后再遇到新的状态题就不会觉得动态规划是玄学了。