当前位置：首页 > news >正文

LeetCode 63：Unique Paths II - 带障碍网格路径问题的完整解析与面试技巧

news 2026/3/27 2:21:42

题目与背景

LeetCode 63：Unique Paths II 要求在一个带障碍的网格中，统计从左上角走到右下角的不同路径数。机器人每次只能向右或向下移动，遇到障碍（值为 1）则不能踩该格。github+1

和经典的 Unique Paths（无障碍版本）相比，这题唯一的变化就是：某些格子不能走，这直接影响 dp 初始化和状态转移的细节。krybot+1

问题建模与状态定义

网格与输入

输入：obstacleGrid，大小为 m×n。
- obstacleGrid[i][j] == 0：空地，可以走。
- obstacleGrid[i][j] == 1：障碍，不能走到该格，也不能通过该格继续前进。learncodingfast+1
目标：从(0, 0)走到(m-1, n-1)的不同路径数。

状态定义

常见、清晰的定义是：

用一个同样大小的二维数组dp。
定义：dp[i][j]表示从起点(0,0)到达位置(i,j)的不同路径数。codeanddebug+1

好处：

含义直观：“走到这个格子的所有方式有多少”。
障碍就可以体现在该格的dp[i][j] = 0，后面状态转移自然会"看不到"这条路。

边界情况与初始化细节

这一题最容易在"起点 / 终点 / 第一行 / 第一列"这些边界上出 bug，面试官也很爱抠这些细节。simplyleet+1

1. 起点和终点是否是障碍

关键问题一：如果起点就是障碍怎么办？

如果obstacleGrid[0][0] == 1，那从一开始就无路可走，直接返回 0。
否则才能令dp[0][0] = 1，表示"起点有 1 种方式被到达（就是站在那）"。learncodingfast+1

关键问题二：如果终点是障碍怎么办？

如果obstacleGrid[m-1][n-1] == 1，也不可能走到终点，答案也必须是 0。
常见做法是：直接前置判断返回 0；或者在遍历中，如果终点本身是障碍，最终算出来也会是 0。algo+1

2. 第一行和第一列的初始化

机器人只能向右或向下走，这意味着：

第一行的每个格(0, j)只能从左边(0, j-1)走过来。
第一列的每个格(i, 0)只能从上边(i-1, 0)走过来。geeksforgeeks+1

因此：

对第一行：

如果当前位置没有障碍，并且左边的dp[0][j-1]还能到达（> 0），则dp[0][j] = dp[0][j-1]。
一旦遇到障碍或左边已经是 0，该行后面的格子都应该是 0（再也到不了）。simplyleet

对第一列：

类似：如果当前位置不是障碍，并且dp[i-1][0] > 0，则dp[i][0] = dp[i-1][0]，否则为 0。geeksforgeeks

**注意：**你的原思路中写的是"if i == 0 && grid[i][j - 1] != 1 …“，这是直接看"左边是不是 1”，而正确的关注点应该是"左边的路径数是不是 0"（是否已经被障碍截断），这一点很容易在面试中被追问。algo+1

核心状态转移与常见误区

正确的状态转移公式

在非边界（既不在第一行，也不在第一列）时，机器人到达(i, j)的方式只来自两边：

上边(i-1, j)。
左边(i, j-1)。codeanddebug+1

因此，在当前格不是障碍的前提下：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

实现时常见的套路是：

for i in [0..m-1]: for j in [0..n-1]: if obstacleGrid[i][j] == 1: dp[i][j] = 0 // 当前位置是障碍，无法到达 else if i == 0 && j == 0: dp[i][j] = 1 // 起点已经在前面处理过（或这里特殊处理） else if i == 0: dp[i][j] = dp[i][j-1] else if j == 0: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j-1]

如果提前对起点和终点做了"是障碍就返回 0"的判断，上面可以稍微化简，但思想一样。krybot+1

典型误区 1：检查"左/上是否是障碍"

你原来的转移逻辑类似：

if i == 0 && grid[i][j-1] != 1: dp[i][j] += dp[i][j-1] ... else: if grid[i][j-1] != 1: dp[i][j] += dp[i][j-1] if grid[i-1][j] != 1: dp[i][j] += dp[i-1][j]

这里有两个问题：

不需要再看grid[i][j-1]或grid[i-1][j]是否为 1。
- 因为当左边或上边是障碍时，那一格的 dp 已经被设为 0，不会再对结果有贡献。你只需要简单地"左 + 上"。algo+1
你遗漏的是"当前格grid[i][j]是否是障碍"的判断。
- 当前格是障碍时必须直接dp[i][j] = 0，而不是看左右是不是障碍。codeanddebug+1

面试官典型问法：

“如果grid[i][j] == 1，你的代码会怎么处理dp[i][j]？”
“既然障碍格的 dp 已经是 0，你为什么还要再检查grid[i][j-1] != 1呢？”

典型误区 2：if/else 结构容易出 bug

你写的是类似：

if i == 0 && ... if j == 0 && ... else ...

注意这里是两个 if + 一个 else，而不是 if/else if/else。在很多语言里，else 只会和最近的 if 绑定，如果缩进或括号没处理好，很容易出现：

既走了前面的 if，又进了后面的 else，导致对同一个dp[i][j]重复累加或覆盖。

面试官很喜欢让你写出一段实际代码，然后问你："这个 else 是对应哪一个 if 的？"借此检查你对控制流的理解。

完整步骤与伪代码

结合上面所有讨论，可以把整套解法整理为一个标准的二维 DP 博客模板。

步骤概览

获取m = obstacleGrid.length,n = obstacleGrid[0].length。
如果起点或终点是障碍，直接返回 0。
建立 m x n 的 dp 数组，初始化全为 0。
设置dp[0][0] = 1（在确认起点不是障碍之后）。
遍历整个网格，按行列填充：
- 若当前位置是障碍，dp[i][j] = 0。
- 否则根据是否在第一行/第一列或普通位置，做状态转移。
返回dp[m-1][n-1]作为答案。krybot+2

伪代码示例

下面是一份偏接近实际代码的伪代码，方便直接搬到博客中（改成对应语言语法即可）：

function uniquePathsWithObstacles(obstacleGrid): m = len(obstacleGrid) n = len(obstacleGrid[0]) // 起点或终点是障碍，直接无解 if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1: return 0 dp = array[m][n] filled with 0 dp[0][0] = 1 for i in range(0, m): for j in range(0, n): if obstacleGrid[i][j] == 1: dp[i][j] = 0 // 当前格是障碍，无法到达 else if i == 0 and j == 0: dp[i][j] = 1 // 起点，已处理，可以保留 else if i == 0: dp[i][j] = dp[i][j-1] else if 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]

整体时间复杂度为 O(m×n)，空间复杂度为 O(m×n)。也可以进一步压缩空间到 O(n)，但在面试中优先写清楚二维版即可。youtubecodeanddebug

面试视角：如何从你原思路到标准答案

最后，把"面试官会问你什么"也总结成一段，可直接作为博客中的"常见错误 / 面试官追问点"。

起点是障碍怎么办？（是否提前返回 0，dp[0][0]如何设置）
终点是障碍怎么办？
你为什么在转移时检查左/上是不是障碍，而不是只看dp[i-1][j]、dp[i][j-1]？
当前格grid[i][j]为障碍时，你目前的代码会不会给它一个非 0 的 dp 值？
如果第一行中间出现障碍，你的逻辑能不能保证后面都变成 0？
你的 if / if / else 控制流是否会对同一个dp[i][j]重复赋值？
dp[m-1][n-1]的索引写法是否会越界？（比如你原先的dp[obstacleGridSize - 1][obstacleGridColSize[obstacleGridSize - 1]]）。