企业官网建设流程全解析

LeetCode 63「不同路径 II」是很多人从入门动态规划到真正会写动态规划之间的一道坎。这道题表面上是第 62 题的简单升级，多了一个障碍物判断，但实际写起来，十个里至少有六七个会在第一行、第一列的初始化环节翻车。如果你已经能独立做出 62 题，却在这道题上卡了半小时以上，那说明你缺的不是 DP 思路，而是对边界条件的敏感度。这篇文章不打算重复官方题解那种轻描淡写的推导，我想结合自己刷题和面试的经验，把状态定义、转移方程、初始化、滚动数组、以及最容易踩的坑全部聊透。目标读者是准备笔试面试的应届生、想补 DP 基础的后端开发者，也包括所有想把这一类路径计数问题一次性弄明白的人。

1. 题目到底在问什么

1.1 一句话版本与原始题面

先把这个问题的原始定义说清楚：给定一个 m 行 n 列的网格 obstacleGrid，每个格子是 0 或 1，0 表示可以通行，1 表示障碍物。机器人从左上角 (0,0) 出发，每一步只能向右或者向下移动，要求在移动过程中不经过任何障碍格，最终到达右下角 (m-1,n-1)，返回一共有多少条不同的路径。

这句话里值得圈出来的点有三处：只能向右或向下，这就保证了路径不会回头；障碍物不能经过，意味着障碍格对所有可能路径是一个绝对的阻断；问的是“多少条”，而不是“最短路径”或“是否存在路径”，所以计数类的动态规划是最自然的解法方向。

很多人在看这个题目时会觉得“不就是 62 题加个 if 判断吗”，等你真正动笔写的时候就知道，多出来的这个判断远没有想象中简单。它同时干扰了初始化逻辑、转移逻辑以及滚动数组的复用逻辑，任何一个环节处理错了，结果就会莫名其妙地多算或少算。

1.2 用 3x3 的网格手工推一遍

先动手推一个最简单的例子，这样后面讲状态转移时不会空对空。假设网格是：

0 0 0 0 1 0 0 0 0

机器人从左上角到右下角，中间 (1,1) 是障碍。手工数一下，能走的路径有几条？答案是 2 条：一条是“先向右到 (0,2) 再向下绕过障碍”，另一条是“先向下到 (2,0) 再向右绕过障碍”。中间那格被堵住之后，原本经过它的两条路径都被切断，剩下恰好两条绕行路径。

这个例子也说明了一个直观规律：每个格子的可到达路径数，等于它上方格子的路径数加上它左边格子的路径数，但如果这个格子本身就是障碍，那么它的路径数直接是 0，同时它也不能给下方和右方的格子“输送”任何路径。这个观察就是整个 DP 解法的全部灵魂。

1.3 和第 62 题的真正差异

第 62 题是同一张网格但没有障碍物，绝大多数题解会先把第一行和第一列全部填成 1，从 (1,1) 开始套状态转移。这个“全部填 1”的操作在 63 题里就直接失效了：如果第一行的第三个格子是障碍，那么 (0,3)、(0,4) 以及后面所有靠第一行走的格子都不可能到达，路径数应该是 0 而不是 1。

换句话说，62 题的初始化是“无条件填 1”，63 题的初始化是“遇到障碍就截断，后面的格子全部归 0”。这个差异看起来只有一行代码的区别，但正是它拦截了大批刷题者。很多人写完 62 题后带着惯性来写 63 题，第一行第一列还在用全 1 的方式初始化，样例一跑就挂。

从这个角度讲，63 题考察的其实不是 DP 思路本身，而是你能不能识别出“障碍物如何影响递推边界”。这种能力在实际业务代码里同样重要，几乎所有状态类问题都会遇到“某个条件一旦触发，后续状态全部失效”的场景。

2. 为什么是 DP：状态设计与转移方程的由来

2.1 暴力递归为什么不能直接用

把问题退回到最朴素的想法：机器人每一步有两个选择，向下或向右，最多需要走 m + n - 2 步，如果完全不考虑障碍物，暴力枚举所有路径是 O(2^(m+n)) 的复杂度。m 和 n 稍大一点，比如 30x30，这个数字就是天文数字，任何机器都跑不完。

再进一步，就算用带剪枝的递归去枚举所有“能走”的路径，本质上还是在枚举路径本身，而路径的数量本身就可能非常大。比如一个 20x20 的无障碍网格，路径数是 C(38,19)，结果量级在 10 的 10 次方以上，你根本不可能把每一条都列出来再数。所以这道题要求的是“计数”而不是“枚举”，计数必然要走组合或者递推的路子。

2.2 状态定义：dp[i][j] 到底存什么

动态规划的第一步永远是定义状态。这里最自然的状态定义是：dp[i][j] 表示从起点 (0,0) 出发，走到格子 (i,j) 一共有多少条不同的路径。

为什么要这样定义？因为路径的计数满足“叠加原理”：到达某个格子的每一条路径，要么是从它上方格子走过来的，要么是从它左边格子走过来的，这两部分不会重复，也没有遗漏。只要把到达上方格子的路径数和到达左边格子的路径数加起来，就一定是到达当前格子的路径数。这是一种非常典型的“无后效性”结构，也就是 dp[i][j] 的值只依赖它之前已经被算出来的邻居状态，不需要关心这些路径具体长什么样。

这个状态定义也是后续所有扩展（滚动数组、输出具体路径、带权重）的基础。很多人面试时喜欢一上来就写转移方程，我觉得正确顺序是先说清楚状态定义，因为一旦状态定义有偏差，后面的方程写得再漂亮也是空中楼阁。

2.3 转移方程是怎么凑出来的

有了状态定义，转移方程就水到渠成：如果 grid[i][j] 是障碍物，dp[i][j] = 0；否则 dp[i][j] = dp[i-1][j] + dp[i][j-1]，其中越界的部分按 0 处理。

这里最关键的细节是：必须先判断“当前格子是不是障碍”，再决定要不要执行加法。如果反过来，先加了再判断障碍，那么障碍格就会错误地从上方和左边继承路径数，导致整个网格的计数全部走偏。

还要注意，障碍格不仅自己为 0，它还相当于一堵墙，把从某个方向过来的路径全部阻断。体现在转移方程里，就是它不会给下方和右方的格子提供任何非零的 dp 值，因为 0 加进去不影响结果。这个“自动阻断”的特性，是这道题能用纯 DP 轻松解决的根本原因。

2.4 初始化为什么是重灾区

初始化要回答两个问题：dp[0][0] 等于多少，以及第一行、第一列怎么处理。

dp[0][0] 的答案很朴素：如果起点是障碍物，那么一步都迈不出去，答案是 0；否则从起点到起点只有一条路径，答案是 1。很多人在这一步就直接踩坑，默认 dp[0][0] = 1，完全没考虑起点被堵死的特殊情况。

第一行和第一列的初始化，正确做法是沿着边从起点一路扫过去，遇到第一个障碍物之前的所有格子都继承上一个格子的值，遇到障碍物之后的所有格子全部是 0。这个逻辑其实和转移方程是统一的：第一行的格子没有“上方”来源，第一列的格子没有“左边”来源，唯一来源就是唯一的那个方向，而障碍格会自动截断。为了让代码统一，我通常不单独做第一行第一列的初始化，而是让所有格子都走同一个双层循环，只对越界的部分以 0 处理，这样逻辑最少，最不容易出错。

3. 完整实现：二维版、滚动数组版与原地版

3.1 二维 DP：最直观、不容易错的版本

直接上代码，Python 实现如下：

def unique_paths_with_obstacles(grid): m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)] # 起点本身可能是障碍 dp[0][0] = 0 if grid[0][0] == 1 else 1 for i in range(m): for j in range(n): if grid[i][j] == 1: dp[i][j] = 0 continue if i > 0: dp[i][j] += dp[i - 1][j] if j > 0: dp[i][j] += dp[i][j - 1] return dp[m - 1][n - 1]

这个版本有几个细节值得展开说一下。

第一个细节：dp[0][0] 在循环外先赋值，是因为循环到 (0,0) 时，它既没有上方也没有左方来源，如果不提前赋值，它会一直保持 0。我把这行写在循环前，而不是试图在循环里用一个 if 去特判，是为了让主循环更干净。

第二个细节：循环里的 if grid[i][j] == 1 分支会在当前格是障碍时把 dp[i][j] 清零，这个判断同时覆盖了 (0,0) 的情况。也就是说，即使你在循环外不小心把障碍起点的 dp[0][0] 赋成了 1，循环内也会把它纠正成 0。所以循环外那句初始化的写法可以稍微随意一点，只要记得起点为非障碍时赋 1 即可。

第三个细节：对于 i > 0 和 j > 0 的判断，分别对应“有上方”和“有左边”两种情况。第一行第一个格子两个条件都不满足，保持初始值；第一行其他格子只有上方不满足但左边满足，所以只会加左；第一列其他格子同理。

3.2 滚动数组优化：把空间从 O(mn) 压到 O(n)

二维数组的 m x n 空间在多数场景下是可接受的，但既然题目考 DP，空间优化往往是面试时必然会问到的一步。滚动数组的思路是：观察转移方程，dp[i][j] 只依赖 dp[i-1][j] 和 dp[i][j-1]，也就是说当前行计算时只需要上一行的数据，更早的行完全没有保留的必要。

用一维数组 dp[j] 来滚动，进入第 i 行时，dp[j] 还保存着上一行第 j 列的结果，它代表 dp[i-1][j]；而 dp[j-1] 在当前行已经被更新过，它代表 dp[i][j-1]。所以核心操作就是：如果当前格不是障碍，dp[j] = dp[j] + dp[j-1]。如果当前格是障碍，先 dp[j] = 0，阻止它向下方和右方传递任何路径。

代码长这样：

def unique_paths_with_obstacles_1d(grid): m, n = len(grid), len(grid[0]) dp = [0] * n dp[0] = 0 if grid[0][0] == 1 else 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]

这个版本看起来比二维版还短，但它隐含了一个容易踩的坑：j 等于 0 的时候，elif j > 0 不会执行，dp[0] 直接沿用上一行的值。这其实是正确的语义，因为第一列每个格子只有上方来源，dp[0] 在进入新一行时必须保持上一行第一列的状态。但如果当前行的第一列是障碍，前面的 if 已经把 dp[0] 清零了，后续行也自然继承 0，逻辑依旧成立。

我建议第一次写滚动数组时，不要直接抄这个最短版本，而是先按二维版本写，然后逐行对照着改。比如对照 dp[i-1][j] 和 dp[i][j-1] 分别变成了什么值，确认没有把“继承”和“累加”的关系搞混，再落地成代码。

3.3 原地修改的可行性讨论

还有一个更极端的做法：直接在 obstacleGrid 上原地记录路径数，把额外空间压缩到 O(1)。思路是先把所有障碍格标记为 0，然后从 (0,0) 开始按顺序填充。代码可以这样写：

def unique_paths_with_obstacles_inplace(grid): m, n = len(grid), len(grid[0]) if grid[0][0] == 1: return 0 grid[0][0] = 1 for j in range(1, n): grid[0][j] = 1 if grid[0][j] == 0 and grid[0][j - 1] == 1 else 0 for i in range(1, m): grid[i][0] = 1 if grid[i][0] == 0 and grid[i - 1][0] == 1 else 0 for i in range(1, m): for j in range(1, n): if grid[i][j] == 1: grid[i][j] = 0 else: grid[i][j] = grid[i - 1][j] + grid[i][j - 1] return grid[m - 1][n - 1]

虽然空间确实最优，但我不推荐在面试时主动写这个版本。原因有两个：第一，它修改了输入数组，如果后续逻辑还要依赖原始的障碍分布，会产生隐蔽的 bug；第二，原地填充时，障碍格被改成 0 之后，代码的可读性明显变差，面试官需要花精力理解“这里的 0 到底是原来的通路，还是被清零的障碍格”。除非面试官明确要求“额外空间尽量小”，否则滚动数组已经是足够优雅且安全的最优解。

4. 边界条件与测试用例设计

4.1 必测的四类输入

经验之谈，刷这道题最容易挂掉的不是复杂的大样例，而是下面这几类看着很简单的边界输入。我在本地整理了一份固定测试清单，每次写完代码先跑一遍再提交，能省下大量反复提交的时间。

第一类，起点就是障碍。比如 grid = [[1]]，此时起点即终点，但起点根本不能站人，结果应该是 0。再比如 grid = [[1, 0]]，机器人根本无法出发，也应该是 0。

第二类，终点就是障碍。比如 grid = [[0, 1]]，机器人只能向右移动一步，结果应该是 0。很多实现会把终点路径数算成 1，因为转移方程根本不会检查终点的障碍属性，必须靠主逻辑里对每个格子的障碍判断兜底。

第三类，单行或单列。比如 grid = [[0, 0, 1, 0]]，机器人只能向右移动，一旦路径上出现障碍，后续全为 0，结果就是 0。而 grid = [[0, 0, 0]] 没有障碍，结果应该是 1。单行单列最容易暴露初始化截断逻辑的错误。

第四类，全障碍或全通的大网格。全通网格其实是 62 题的结果，可以用来和公式 C(m+n-2, m-1) 交叉验证。全障碍网格除了起点以外全是 1，结果一定是 0。这两类用例可以快速检验整体逻辑是否正确。

4.2 手工画一个状态表验证结果

下面用一个 3x4 的网格来手工推导，障碍设在 (0,2) 和 (2,1)，也就是：

0 0 1 0 0 0 0 0 0 1 0 0

用二维 dp 逐格填写最终状态，结果如下表：

验证一下：网格右上角 (0,3) 的路径数为 0，因为第一行在 (0,2) 被障碍截断，无法从左边继续向右；但 (1,3) 的路径数是 2，因为可以通过第二行绕过障碍。右下角 (2,3) 的路径数是 4。每一步验证时，把 dp[i][j] 和“上方加左边”对照着看，能帮助你在调试时快速定位是哪一行逻辑出了问题。

这个手推过程看起来笨重，但它恰恰是理解“障碍物如何阻断路径传递”的最快方式。我见过不少直接抄题解的人，代码一遍过，但问他为什么第一行从第三列开始全是 0，答不上来。真上了面试，追问两轮就露馅。

4.3 复杂度分析与语言细节

二维版的时间复杂度是 O(mn)，因为每个格子恰好访问一次；空间复杂度是 O(mn)；滚动数组版时间不变，空间降到 O(n)。这个分析几乎是送分题，但很多人会漏掉“遍历过程中每个格子只访问一次”这个前提，把它和多源 BFS 之类的解法混淆。

另外讲一个容易被忽略的问题：溢出。62 题在极端情况下路径数会非常大，63 题因为有障碍物通常结果会小一些，但在全通大网格的边界用例下同样可能超过 32 位 int 的范围。在力扣的测试数据里，这道题用 int 基本能过，因为 m 和 n 的限制没到最极端，但本地自测或者面试手写时，用 C++ 和 Java 的同学不妨把 dp 数组声明成 long，成本几乎为零，还能免去很多隐患。Python 由于整数是任意精度的，完全没有这个烦恼。

5. 常见错误排查与面试复盘

5.1 高频 Bug 一：障碍格没有先清零

最常见的错误是只在计算路径数时跳过障碍格，而不是主动把 dp 值置 0。比如有人会写：

if grid[i][j] == 1: continue

continue 确实跳过了累加，但 dp[i][j] 仍然保留着从上方或者左边继承来的值吗？不会，因为 dp[i][j] 在二维数组里初始是 0，跳过累加后它还是 0，看起来没问题。但在滚动数组版本里情况就完全不一样了：dp[j] 在进入当前行时还保留着上一行的值，如果遇到障碍只是 continue 而不清零，下一行或者同一行的后续操作就会把它当作有效路径继续累加，结果迅速膨胀。

所以这条经验可以总结成一句话：遇到障碍格，必须显式 dp[i][j] = 0（在二维版里是“置 0”，在滚动数组版里是“清零后再继续”），而不是简单地跳过。

5.2 高频 Bug 二：第一行第一列用了 62 题的初始化方式

把 62 题的“第一行第一列全部填 1”照搬过来，是另一种高频错误。比如有人会写：

for j in range(n): dp[0][j] = 1 for i in range(m): dp[i][0] = 1

遇到障碍后，第一行后面的格子依然被填成 1，最终答案会被明显高估。正确的做法是逐格判断，遇到障碍后停止填充，后面全部为 0。最稳的方式就是我在第 3 节给出的统一循环写法，让所有格子都走同一个转移逻辑，只在越界处做保护，这样第一行第一列的特殊性就自动消失了。

5.3 高频 Bug 三：滚动数组复用时的脏数据

滚动数组虽然代码短，但出问题的概率反而更高。一个典型的错误是忘记在每行开始前重置某些列的状态，导致上一行的路径数被错误地带到当前行。还有一个隐蔽的写法问题：如果内层循环从右往左遍历，转移方程会变成 dp[j] += dp[j+1] 吗？不会，因为本题机器人只能向右或向下，状态只依赖左和上，从右往左遍历会破坏 dp[j-1] 的“当前行”语义，结果必然出错。

检查滚动数组正确性的办法有两个：一是打印每一行处理完之后的 dp 数组，和二维版逐行对照；二是把遍历方向、状态依赖关系写清楚，遇到方向相关的题目（比如带左移、右移的变体）时尤其要谨慎。

5.4 面试官可能会追问的变体

如果面试官在 63 题之后继续加码，通常会把问题引向下面几个方向。

第一个追问是：如果障碍物会随机出现在某些格子，让你求期望路径数，怎么改？答案是概率 DP，每个格子的期望路径数等于上方期望加左方期望，障碍格期望为 0，但前提需要已知障碍概率分布。

第二个追问是：如果要求输出任意一条可行路径而不是计数，怎么处理？思路是先跑一遍 DP 得到路径数的网格，然后从终点反向回溯，每次优先走向上或向左的格子中路径数非零的方向。注意回溯时依然要避开障碍格。

第三个追问是：如果机器人可以上下左右四个方向移动，但路径不能重复访问同一个格子，怎么做？这个问题就不能简单套用当前 DP 了，它涉及到搜索加状态压缩，复杂度会明显上升。这类追问本质是考察你是否理解当前 DP 成立的“无环依赖”前提。

6. 从这道题延伸出去：路径类 DP 的通用套路

6.1 62、63、64 这三题的共同结构

力扣里路径计数类的经典三连是第 62 题、第 63 题和第 64 题（最小路径和）。它们的网格模型完全一样，区别只在于：

• 62 题：统计路径条数，没有障碍，dp 值累加；
• 63 题：统计路径条数，有障碍，障碍格 dp 置 0；
• 64 题：求最小路径和，网格里的数字是权重，转移方程从加法变成取 min，但遍历方向和边界处理方式完全一致。

把这三道题放在一起学，比单独刷某一道的效率高得多。你会发现只要掌握了“网格 DP 的三件套”——状态定义、转移方向、边界初始化——稍加变化就能套进这三个看似不同的题。

这也是一道典型的“背模板容易、理解边界难”的题目。我不反对在刚开始刷题时参考模板，但建议至少花半小时自己做一遍手推表，把每个格子为什么是这个值讲明白。想明白这个，你才算真正会了路径类 DP。

6.2 如果要求输出一条具体路径

假设题目要求不只是计数，还要输出一条从左上到右下的路径。做法非常简单：先跑一遍 DP，得到每个格子的 dp 值，然后从终点反向回溯。回溯到 (i,j) 时，看上方和左方哪个格子的 dp 值不为 0，就往那边走，优先顺序可以自己定，只要保证方向合法且不是障碍。走到起点就把路径逆序输出。

这里有一个容易出错的地方：不能只看 dp 值是否大于 0 就贸然选择方向，还必须确认那个方向的格子本身不是障碍。因为障碍格的 dp 值是 0，所以“dp 值不为 0”这个条件天然排除了障碍，理论上不会踩坑。但如果你在滚动数组里用了脏数据，就可能出现“路径数大于 0 但实际不该走过去”的假象，所以输出路径前最好再用原始 grid 做一次障碍检查，双保险。

6.3 障碍物会变化的情况

最后聊一个稍微进阶的变体：如果网格里有若干障碍物会随着时间变化，比如某个障碍物在特定时间点消失，怎么求某时刻到达终点的路径数？这类问题通常要引入时间维，变成三维 DP，dp[t][i][j] 表示在时刻 t 位于 (i,j) 的路径数。转移时要考虑每个时刻哪些格子能走，本质上和本题的转移逻辑完全一致，只是多加了一维。

这类变体在面试中不一定考，但理解“把额外约束加进状态维度”的思路，对解决很多更复杂的 DP 题非常有帮助。遇到不在常规套路里的新题，先想想能不能通过加一维状态来容纳多出来的条件，这比硬套模板可靠得多。

我自己刷题的习惯是：每做完一道路径类 DP，都会顺手把它的变体方向在笔记里写一行，比如“能不能反向走”“能不能带权”“能不能多障碍”，之后再遇到类似题目时检索起来非常快。这道 63 题能延伸出来的变体数量很可观，值得多花半小时做这样一份笔记。

还有一点要提醒：面试时如果让我现场写这道题，我会先跟面试官说清楚思路——状态定义、转移方程、初始化、空间优化，然后再动笔。写完之后主动跑几个边界用例，比如起点是障碍、终点是障碍、单行单列，基本就能把分数稳住。这道题考察的从来都不是你能不能默写转移方程，而是你能不能严谨地把所有边角情况都照顾到。搞定了这道题，后面再遇到带约束的网格 DP，你的心态会稳很多。