做 LeetCode 的 dp 专题刷到第 63 题时很多人会以为它只是 62 题的「加了个 if 判断」结果一写就错。这道「不同路径 II」确实只多了障碍物但恰恰是这一点变化把很多的初始化细节、边界判断、空间优化里的坑全都暴露出来了。这篇文章我会把这道题从题目本质、状态推导、代码落地到面试追问完整拆一遍适合正在刷动态规划的新手也适合准备面试但想把这个系列吃透的选手。1. 先看懂这张带墙的地图问题本质与游戏规则1.1 用一句话概括这个题目在算什么题目给的是一个 m 行 n 列的网格每个格子上要么是 0空地要么是 1障碍物。一个机器人从左上角 (0,0) 出发每次只能向右移动一步或者向下移动一步目标是到达右下角 (m-1,n-1)。问总共有多少条不同的路径前提是路径不能穿过任何一个障碍物格子。这里的关键词是「不同路径」——不是最短路径不是经过所有格子的路径而是所有合法的、从起点到终点、每一步只向右或向下的移动序列。路径的「不同」体现在每一步的选择序列不同。比如对于一个 3×3 的无障碍网格你可以先走两步右再走两步下也可以右下右下这些都是不同的路径。这一点要先想清楚题目问的是组合意义上的路径数量不是步数最少的那条路。步数其实固定了因为只能向右和向下所以任意一条合法路径的长度一定是 (m-1) (n-1)没有任何绕路的空间。路径的区别只在于「向右」和「向下」这两个动作在序列里出现的位置。这样一来整个问题就变成了一个很经典的组合计数问题而障碍物的出现会把一部分组合方案从这个总数里剔除。1.2 隐藏的几个游戏细节这种题目表面上是看图说话但真正写代码时最容易翻车的恰恰是题目里那几个「默认常识」。第一机器人每一步的动作是严格受限的。不是你想走哪个方向走哪个方向只有右和下两种选择。这从根源上决定了路径数量的计算方式也是动态规划能用的前提。如果机器人四个方向都能走那这个问题瞬间变成图的路径规划复杂度dp 的状态定义也会完全不同。第二网格里 0 表示空地、1 表示障碍物这是 LeetCode 上常见的约定。别想当然地写成「1 表示可以走、0 表示不能走」我见过不少人在把题目从文字描述转换成代码时把判断条件写反白送一个 WA。第三起点和终点本身可能是障碍物。题目没有保证 grid[0][0] 和 grid[m-1][n-1] 一定是 0。这就意味着代码里一定要先做这个判断如果起点就是障碍物机器人根本站不上去直接返回 0终点是障碍物同理。这是最容易漏掉的 corner case很多人在小规模测试用例上跑得通一提交就挂在隐藏用例上多半就是这里的问题。第四网格规模。原题 m、n 都在 100 以内路径数会非常大。无障碍的 100×100 棋盘路径数量是一个几十位的大整数远超 32 位 int 的表示范围。所以如果用 C/Java 写要么用 long要么根据题目要求取模。Python 因为整数无上限倒是不用担心但这个意识必须有。2. 有障碍和无障碍差在哪从 62 题到 63 题的变化点2.1 62 题的状态转移为什么会如此干净既然 63 题叫「不同路径 II」那它的基础就是 62 题「不同路径」。62 题的网格里全是空地问路径总数。这题的 dp 极其经典定义 dp[i][j] 表示从 (0,0) 走到 (i,j) 的路径数量。因为机器人只能从上方 (i-1,j) 或左方 (i,j-1) 到达 (i,j)所以有dp[i][j] dp[i-1][j] dp[i][j-1]这个式子之所以能成立是因为到达某个格子的最后一步只有两种可能从上边下来或者从左边过来。这两种来源互不重叠路径数量直接相加即可。我当年第一次看到这个转移方程时觉得它平平无奇后来才发现这是动态规划里最典型的「无后效性」应用dp[i][j] 的计算只依赖它上面和左边的结果而这些结果在按行、按列遍历时已经被算出来了。初始化的部分也一样第一行和第一列的格子由于只能从起点一路向右或一路向下到达路径数都是 1。这就是 62 题的全貌简单、清晰几乎是一道送分题。2.2 障碍物给状态转移带来真正的变化63 题加了一个障碍物看似只是多加一个判断实际上它同时影响了三件事初始化、状态转移、边界条件。影响最大的是初始化。在 62 题里第一行所有格子都是 1因为从起点一路向右只走这一条路。但在 63 题里如果第一行的某个格子是障碍物那从它开始往右的所有格子都不可达——机器人只能向右走一旦被挡住后面的格子无论如何都到不了。第一列同理。所以初始化时不是无脑填 1而是要「遇到障碍前填 1遇到障碍后全部填 0」。这个细节最坑的地方在于你可能会想当然地认为「第一行的格子如果本身是障碍物就填 0不是障碍物就填 1」然后写出一个简单的循环。但如果第一行第 2 个格子是障碍物第 3 个格子是空地那第 3 个格子的路径数实际上是 0因为它被第 2 个障碍物挡死了。只判断当前格子是不是障碍物是不够的还必须继承左边格子的状态。第一列同理要继承上边格子的状态。再一个变化在状态转移。62 题的转移方程直接相加不需要任何附加条件63 题则要回答一个问题这个格子本身是不是障碍物。如果是障碍物那么它没有任何路径可达dp[i][j] 直接等于 0如果不是障碍物dp[i][j] 才等于上方路径数和左方路径数的和。这个判断千万不能漏漏了结果会大得多因为你会把不可达的格子也算出一个路径数来。还有一个隐藏变化终点的判断。终点是障碍物直接返回 0 这件事放在 62 题里根本不存在但在 63 题里如果不处理后面 dp[m-1][n-1] 的计算会因为转移方程里的障碍判断而自然变成 0结果倒也不算错。但问题在于其他的格子可能已经算了半天这对性能是一种浪费。更进一步如果你不是用 dp 而是用递归或者别的方式求解起点终点的判断就是必要的不能依赖转移方程兜底。所以在写代码时我的习惯是一开始就判断快速返回而不是绕一圈。3. 状态定义与转移方程的完整推演3.1 为什么状态要定义为「到达某个格子的路径数」有些人一上来就困惑为什么 dp[i][j] 表示路径数而不是表示别的这里的关键在于我们要计数的对象本身——路径。路径是一步一步走出来的每一步只关心「当前在哪个格子」而不关心此前是怎么来的。换句话说从起点到当前格子的路径数可以被拆解为「从起点到当前格子上方格子的路径数」加上「从起点到当前格子左方格子的路径数」然后各自再走最后一步。这种用「当前所在位置」作为状态、用「怎么走到这里」来累加的模式就是计数型动态规划的典型套路。用生活类比来说假设你在一个只有右转和下转的单行道迷宫里数有多少种方式走到某个路口那你根本不用关心前一个路口是哪条路进来的只需要把「能走到上面那个路口的方案数」和「能走到左边那个路口的方案数」加起来就是到达当前路口的方案数。因为到当前路口的最后一步只可能来自这两个相邻路口。这就是状态定义的最底层逻辑。3.2 状态转移方程的两个版本我把转移方程写成两种形式方便不同基础的人理解。完整形式考虑障碍是这样的如果 grid[i][j] 1 dp[i][j] 0 否则 dp[i][j] dp[i-1][j] dp[i][j-1]这个写法很直白但不是写代码时的最优写法。写代码时为了避免判断 i-1、j-1 是否越界通常有两种处理方式一是单独初始化第一行和第一列循环从 (1,1) 开始二是在 dp 数组外面多包一圈 0让 i-1 和 j-1 在边界时自然指向 0省掉越界判断。我个人更推荐第一种因为它的思路更贴近手算推导也不容易在包圈时搞混下标。第二种在写「周边补零」类型的题目比如岛屿类问题里很好用但在这里会让 dp 数组的下标和 grid 的下标错位需要额外小心。另一种写法是把判断合并进转移方程dp[i][j] (grid[i][j] 1) ? 0 : dp[i-1][j] dp[i][j-1]这个写法在代码上很干净但隐含了「障碍格直接置 0」的逻辑初学者容易在后面调试时忘记这一层含义。我建议你在草稿纸上先写完整形式真实现代码时再压缩。3.3 初始化是第一道鬼门关我前面已经提到初始化的坑这里把它彻底讲透。初始化要分三块处理。第一块是起点。dp[0][0] 的值取决于 grid[0][0] 是否为障碍物。如果是障碍物直接返回 0整个数组都不用算了如果不是dp[0][0] 1表示从起点到起点有一条路径——什么都不走也算一种方案。第二块是第一行。遍历 j 从 1 到 n-1规则是如果 grid[0][j] 是障碍物dp[0][j] 0否则 dp[0][j] dp[0][j-1]。注意这个「否则」取的是左边格子的路径数不是无条件填 1。这就是 62 题和 63 题初始化最大的区别所在。第三块是第一列。同理遍历 i 从 1 到 m-1如果 grid[i][0] 是障碍物dp[i][0] 0否则 dp[i][0] dp[i-1][0]。为什么第一行第一列不能像 62 题那样全部填 1很简单如果 grid[0][2] 是 1那 grid[0][3] 无论如何都到不了因为机器人只能向右走到 grid[0][3] 必须经过 grid[0][2]这条路被堵死了。它的路径数就是 0而不是靠「一路向右」得到的那条路径——因为那条路径已经不存在了。4. 代码落地的两种方式二维数组版与一维滚动版4.1 先上二维 dp 的标准实现直接看代码Python 版是最好读的def unique_paths_with_obstacles(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) # 起点或终点就是障碍物直接返回 0 if grid[0][0] 1 or grid[m-1][n-1] 1: return 0 dp [[0] * n for _ in range(m)] dp[0][0] 1 # 初始化第一行 for j in range(1, n): if grid[0][j] 1: dp[0][j] 0 else: dp[0][j] dp[0][j-1] # 初始化第一列 for i in range(1, m): if grid[i][0] 1: dp[i][0] 0 else: dp[i][0] dp[i-1][0] # 状态转移 for i in range(1, m): for j in range(1, n): if grid[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]这段代码的关键点有三个一是先判断起点和终点这是我最开始就强调的。注意我用了grid[0][0] 1 or grid[m-1][n-1] 1两个条件一满足就 return 0不需要继续算。二是第一行第一列的初始化必须「继承前一个格子的值」。我见过太多人把这里写成了if grid[0][j] 1: dp[0][j] 0 else: dp[0][j] 1这种写法在 grid[0][2] 是障碍物时会出错grid[0][3] 会被错误地算成 1但实际应该是 0。只有用dp[0][j] dp[0][j-1]才能让障碍物之后的所有格子都变成 0。三是主循环里遇到障碍物直接置 0。很多人的困惑是既然障碍格的 dp 值是 0那它右边和下面的格子会不会受影响答案是会的但不是因为 dp[0][j] 本身是 0而是因为它们依赖的「上方或左方路径数」已经是 0相加之后自然受到抑制。这就是动态规划中「障碍物信息通过状态值传导」的过程。再补充一个 Java 版本方便对比写法class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m obstacleGrid.length; int n obstacleGrid[0].length; if (obstacleGrid[0][0] 1 || obstacleGrid[m-1][n-1] 1) { return 0; } int[][] dp new int[m][n]; dp[0][0] 1; for (int j 1; j n; j) { if (obstacleGrid[0][j] 1) { dp[0][j] 0; } else { dp[0][j] dp[0][j-1]; } } for (int i 1; i m; i) { if (obstacleGrid[i][0] 1) { dp[i][0] 0; } else { dp[i][0] dp[i-1][0]; } } for (int i 1; i m; i) { for (int j 1; j n; j) { 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]; } }4.2 空间优化用一维数组滚动覆盖二维 dp 是好理解但空间复杂度是 O(m*n)。m、n 在 100 以内还好但如果面试官追问或者题目数据范围放大到几千这个内存就会成为瓶颈。更优雅的做法是用一维数组滚动更新把空间压到 O(n)。核心思路是这样的我们按行遍历网格维护一个长度为 n 的 dp 数组。在第 i 行处理完第 j 列之后dp[j] 表示的就是 dp[i][j] 的值。当我们要处理第 i 行的第 j 列时此刻 dp[j] 还没有被更新它代表的其实是 dp[i-1][j]上一行同一列的值而 dp[j-1] 刚刚被更新过它代表的是 dp[i][j-1]当前行左边一列的值。所以转移方程在代码里直接写成dp[j] dp[j] dp[j-1]等等这式子好像没体现障碍物判断放完整的代码里看def unique_paths_with_obstacles(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) if grid[0][0] 1 or grid[m-1][n-1] 1: return 0 dp [0] * n dp[0] 1 # 起点 for i in range(m): for j in range(n): if grid[i][j] 1: dp[j] 0 elif j 0: dp[j] dp[j-1] return dp[n-1]这个版本简洁到只有几行但对理解要求高不少。逐行拆解初始化时 dp[0] 1其他为 0。这里的 dp[0] 1 表示从起点出发的初始路径数相当于二维版本的 dp[0][0] 1。外层循环 i 从 0 到 m-1内层循环 j 从 0 到 n-1。为什么要从 j0 开始因为一维数组要利用「dp[j] 更新前是上一行的值」这个特性如果把第一列单独拿出来初始化逻辑会变乱。直接把起点和障碍判断放在循环里统一处理更干净。在内层循环里遇到障碍物直接 dp[j] 0这一步同时完成了「初始化第一列遇到障碍」和「转移过程遇到障碍」两种情况。如果当前格子不是障碍物并且 j 0则dp[j] dp[j-1]。注意这里不是等号是加等因为 dp[j] 原本还保留着上一行的值dp[i-1][j]加上 dp[j-1]当前行左边的值正好得到 dp[i][j]。这个技巧是空间优化的精髓用一维数组同时存储「上一行」和「当前行」的信息利用遍历顺序自然区分新旧值。你可以把 dp[j] 想象成一张正在被反复擦写的纸处理第 i 行第 j 列时纸上写的是上一行第 j 列的结果处理完第 j 列之后纸上的内容被覆盖成当前行第 j 列的结果供同一行后面的列使用。我第一次看这个优化时觉得特别巧妙但也特别容易晕。建议你一定要在纸上手动走一遍 3×3 的例子把 dp 数组每一步的变化写下来比盯着代码看十遍都管用。比如 grid 是0 0 0 0 1 0 0 0 0初始 dp [1, 0, 0]第 0 行j0, 不是障碍, j0 所以不执行 elifdp [1, 0, 0]j1, 不是障碍, dp[1] 0 dp[0] 1dp [1, 1, 0]j2, 不是障碍, dp[2] 0 dp[1] 1dp [1, 1, 1]第 1 行j0, 不是障碍grid[1][0]0, 不执行 elifdp[0] 保持 1dp [1, 1, 1]j1, 是障碍, dp[1] 0dp [1, 0, 1]j2, 不是障碍, dp[2] 1 dp[1] 1 0 1dp [1, 0, 1]第 2 行j0, 不是障碍, dp[0] 保持 1dp [1, 0, 1]j1, 不是障碍, dp[1] 0 dp[0] 1dp [1, 1, 1]j2, 不是障碍, dp[2] 1 dp[1] 2dp [1, 1, 2]最终 dp[2] 2和二维版本算出来的答案一致。这个手算过程能让你真正理解「dp[j] dp[j-1]」里那个加号是什么意思。4.3 两种方案复杂度对比方案时间复杂度空间复杂度适合场景二维 dpO(m*n)O(m*n)思路直观适合首刷和讲解一维滚动O(m*n)O(n)面试进阶、数据规模大时使用时间复杂度两者完全一样都是必须遍历一遍网格因为每个格子的状态都依赖它上方和左边的状态没有任何格子可以跳过计算。空间上一维滚动从 O(m*n) 降到 O(n)在 m、n 接近 100 时看不出太大差别但如果是 1000×1000 的网格二维 int 数组就要约 4MB一维只需要 4KB差距是千倍级的。这道题在 LeetCode 里还有后续的「不同路径 III」变体到时候熟练运用滚动数组能省不少事。5. 测试用例与隐藏的边界条件5.1 六组手工验证每一组都揭示一个坑直接跑 LeetCode 提交之前我会先用下面这六组用例在本地过一遍。每过一组都能逼出一个潜在 bug。第一组最小规模无障碍网格。grid [[0]]期望输出 1。这一组测的是起点即终点的情况只有一种路径——原地不动。如果代码里没有特殊处理 m1 且 n1 的情况也能通过但要确保不会因为数组越界报错。第二组1 行 n 列网格。grid [[0, 0, 0, 0]]期望输出 1。因为机器人只能一路向右路径只有一条。这一组专门测第一行初始化的逻辑如果初始化写成「遇障碍置 0无障碍置 1」那么这组用例能过但换成第三组就会暴露问题。第三组1 行 n 列网格中间有障碍。grid [[0, 0, 1, 0]]期望输出 0。障碍物在第 2 列把路完全堵死。如果你的初始化写成了「无障碍就填 1」那么 grid[0][3] 会被错误算成 1最终结果错得离谱。这一组是检验第一行初始化是否「继承前值」的照妖镜。第四组起点或终点是障碍物。grid [[1, 0], [0, 0]]期望输出 0。起点是障碍物机器人根本没地方站必须直接返回 0。反过来终点是障碍物也一样。这组测的是代码开头的快速判断是否到位。第五组经典 3×3 中间堵一格。grid [[0, 0, 0], [0, 1, 0], [0, 0, 0]]期望输出 2。所有路径里经过中心格子的那两条都失效了只剩下绕行的两条。这一组最能检验主循环里的障碍判断是否生效。第六组障碍物形成一堵墙把上下隔开。grid [[0, 0, 0], [1, 1, 1], [0, 0, 0]]期望输出 0。整个第二行全是障碍物机器人无法从第一行下到第三行。这一组测的是障碍物的「传导效应」即便每行第一列和最后一列看起来是空的但中间被堵死路径数依然是 0。有些 dp 实现如果只在「当前格子是障碍物时置 0」而不考虑上下层之间的阻断就可能算出一个非 0 的错答案。当然严格按转移方程写不会犯这个错但调试时很容易被这种用例迷惑。5.2 我自己踩过的坑初始化写成了逐格判断我在第一次独立实现这道题时犯过一个特别低级的错误。当时我自认为很熟悉 62 题于是把 63 题的第一行初始化直接写成了for j in range(n): if grid[0][j] 1: dp[0][j] 0 else: dp[0][j] 1写的过程特别顺畅跑示例用例也没问题。直到我拿第三组用例[[0,0,1,0]]去验证才意识到 grid[0][3] 被算成了 1但实际它是不可达的。那一瞬间我意识到问题不在转移方程而是我小看了初始化在带障碍场景里的作用。后来我把初始化改成继承前值并加注释再也没错过。这个经历给我一个教训做带条件的 dp 题目时初始化不能再沿用无条件的经验。每一行、每一列的第一个值怎么算是否依赖前一个格子的状态必须单独推演而不是凭印象照抄旧题解。5.3 为什么不能用纯 DFS 硬算很多新手看到「路径数量」第一反应是深搜从起点出发递归地向右、向下尝试遇到障碍返回到达终点计数加一。这个思路在 3×3 小棋盘上可行但一旦棋盘变大就会爆炸。路径数是组合数级别的大约是 C(mn-2, m-1)100×100 无障碍棋盘的理论最大路径数是一个天文数字DFS 会把每一条路径都实际走一遍时间和空间都无法接受。动态规划的优势在于它对每个格子只算一次用加法把子问题结果累加起来而不是把整条路径展开。这本质上是「用空间换时间」和「用状态合并代替路径枚举」的差别。理解这一点你才真正明白 dp 对这个题是必然选择而不是「因为题目在 dp 分类下所以用它」。6. 面试官会怎样基于这道题做延伸6.1 最常见的三个追问第一问如果网格里每个格子有对应的权值或花费要求计算「从起点到终点的最小路径花费」你还能用 dp 吗能。状态定义从「路径数」变成「最小花费」转移方程从相加变成取较小值dp[i][j] min(dp[i-1][j], dp[i][j-1]) cost[i][j]遇到障碍格可以直接跳过不处理或者把障碍格的 dp 值设为无穷大。这个变体实际上就是另一道 LeetCode 题「最小路径和」的框架和本题只差一个「目标函数」的切换。理解了这个变化你就明白 dp 的状态定义不是死的它服务于你最终要计算的目标。第二问能否把空间压缩到 O(min(m,n))能只要把滚动数组的维度选成较小的那个。如果 m n就按列遍历而不是按行遍历一维数组的长度变成 m。这样空间复杂度进一步优化。原理完全一样只是在实现时要注意循环顺序和 dp[j] 的语义对应关系。第三问如果路径数量非常大超过了 64 位整数范围怎么办一个标准做法是取模。在原题中这个问题没有被强制要求但很多衍生题特别是竞赛题会让你对一个大质数取模比如 10^97。如果取模转移方程不变只需要每次加法运算后% MOD即可。这里有个小坑如果使用 Python 的整数运算不取模也能算对但内存和时间会随着数字位数增长在 C 或 Java 中要明确使用 long long 或取模后的 int。6.2 进阶变体打印一条路径而不是计数计数问题解决了有时面试官会进一步问能不能输出一条从起点到终点的合法路径这种题不用 dp 计数而是用贪心加回溯。思路是先做一次 dp 或者 DFS 判断哪些格子可达然后从终点开始逆推如果终点的上方格子可达就走上方否则走左边。这样一步步回溯到起点得到的路径一定是合法解。但要注意这只是一种可行解不是所有解中「最优」的那个——因为本题的路径长度固定不存在最优概念任何一条合法路径长度都一样。在实现时有一个细节如果某个格子的 dp 值为 0不可达回溯时不能选择它。所以打印路径的代码通常和维护 dp 数组的代码配套使用用 dp 值的正负作为可行性标记。6.3 一个容易被问晕的细节为什么滚动数组要从左往右更新而不是从右往左一维滚动数组的核心依赖是「dp[j] 更新前保留上一行的值」。如果从右往左更新dp[j-1] 已经被更新成当前行的值此时计算 dp[j] 需要的「左边值」就不是上一行的 dp[i][j-1]而是当前行的 dp[i][j-1]得到的答案就会出错。这一点和 0/1 背包问题的滚动数组优化方向正好相反。背包问题里从右往左更新是为了让每件物品只被选一次而本题从左往右更新是为了让「左边的新值」参与当前转移。两者的区别源自状态依赖方向不同背包问题的转移依赖「同行左侧且未更新」的值本题的转移依赖「同行左侧已更新」的值。把这两道题的滚动数组方向放在一起对比记忆是我推荐给你的一个加深理解的小技巧。6.4 障碍物的随机比例对 dp 结果的实际影响还有一个偏工程向的思考障碍物比例对答案的影响。如果一个网格足够大障碍物的密度越高可行路径数下降得越快。当障碍密度超过某个临界值时路径数会迅速趋近于 0甚至很多随机生成的网格根本没有合法路径。这个特性在实际问题中是有用的。比如在机器人的路径规划中地图障碍率超过一定阈值时可能更聪明的做法是直接判定「无可行解」而不是盲目地搜索。在做这类题的工程化版本时可以先算一遍「可达性」如果终点不可达就提前结束省去后续路径规划的开销。LeetCode 的题目虽然只要求计数但理解这一层面的含义能把算法题和真实场景联系得更紧密。写到这里这道「不同路径 II」从题目规则、状态定义、初始化陷阱、二维与一维实现、边界用例到面试延伸就算讲透了。我个人的体会是这道题真正的价值不只是让你会刷一道题而是让你重新审视「动态规划的初始化为什么不能被想当然」这件事。许多 dp 题在转移方程上都长得差不多真正的区分度就在初始化和边界处理上。你在本地手推一遍一维滚动数组的 3×3 过程再对照本篇第六组墙形用例跑一遍以后遇到类似的带约束计数题就再也不会在初始化上栽跟头了。