不同路径 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 × 109。
示例 1
示例 2
模拟答题者思考
1. 最直接：DFS/BFS 枚举所有「只向右或向下」的路径，跳过障碍格，每走到右下角计数 +1——正确但指数级，m,n 可达 100 会超时。
2. 重复在哪里？到达 (i,j) 的路径，最后一步要么从 (i-1,j) 来，要么从 (i,j-1) 来——与 #62 相同的最优子结构；但障碍格不能站脚，到达它的路径数为 0。
3. 子问题定义：设 dp[i][j] = 到 (i,j) 的路径数。若 grid[i][j]==1，dp[i][j]=0；否则 dp[i][j]=dp[i-1][j]+dp[i][j-1]。边界：第一行/列只能从起点单向延伸，遇障碍则后续同向格子全为 0。
4. 手推示例 1：中间 (1,1) 为障碍 dp[1][1]=0，dp[2][2]=dp[1][2]+dp[2][1]=1+1=2，与输出一致。
5. 特判起点：若 grid[0][0]==1，机器人无法出发，直接返回 0——这是 #62 没有的额外边界。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dp[i][j] | int[][] | 定义：从左上角 (0,0) 走到格子 (i,j) 且路径不经过障碍的不同路径条数维护：若 grid[i][j]==1 则 dp[i][j]=0；否则 dp[i][j]=dp[i-1][j]+dp[i][j-1]更新：按行优先双重循环， i 从 0 到 m-1、j 从 0 到 n-1 递增填表 |
grid[i][j] | int | 定义：格子状态，0 可通行、1 为障碍物维护：只读输入，决定当前格子能否作为路径终点 更新：遇到 1 时直接将 dp[i][j] 置 0，不再累加上方/左方 |
dp[0][*] / dp[*][0] | int | 定义：第一行、第一列格子的路径数边界 维护：从起点沿同行/同列只能一直向右或向下；途中遇障碍则该格及之后同向格子均为 0 更新： dp[0][0]=1（若起点非障碍）；i==0 时 dp[0][j]=dp[0][j-1]（遇障为 0）；j==0 时 dp[i][0]=dp[i-1][0] |
prev / cur | int[] | 定义：空间优化时的一维滚动数组，cur[j] 表示当前行第 j 列的路径数维护：每算完一行， prev = cur 作为下一行的「上方」来源更新：障碍格 cur[j]=0；否则 cur[j] += prev[j]（左方已在上一轮循环累加） |
落码步骤
1. 若 grid[0][0]==1，返回 0
2. 创建 dp[n] 滚动数组，dp[0]=1，按行遍历 i 从 0 到 m-1
3. 内层 j 从 0 到 n-1：若 grid[i][j]==1，设 dp[j]=0；否则若 j>0，dp[j]+=dp[j-1]（上方值已在 dp[j] 中）
4. 返回 dp[n-1]
5. 二维写法：双重循环填 dp[i][j]，边界行/列单独处理「遇障截断」逻辑
代码实现
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
if obstacleGrid[0][0] == 1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[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] # 上方(旧dp[j]) + 左方(dp[j-1])
return dp[n - 1]class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid[0][0] == 1) return 0;
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<int> dp(n, 0);
dp[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else if (j > 0) {
dp[j] += dp[j - 1]; // 上方 + 左方
}
}
}
return dp[n - 1];
}
};
// 时间 O(mn)，空间 O(n)复杂度分析
O(m × n)
O(n)（滚动数组）
常见坑
起点有障碍未特判：grid[0][0]==1 时应返回 0，否则 dp[0][0] 会被错误地当作 1。
障碍格仍做递推：遇到 grid[i][j]==1 必须将 dp[i][j] 置 0，不能累加上方/左方，否则会把「经过障碍」的路径计入。
第一行/列边界照抄 #62 全填 1：有障碍时同向后续格子应为 0（路径被截断），需用 dp[0][j]=dp[0][j-1] 而非固定 1。
必测边界 Case
[[1,0],[0,0]] → 0（机器人无法出发）
[[0,0],[0,1]] → 0（无法到达终点格）
[[0,0],[0,0]] → 2（退化为 #62 的 2×2 网格）
[[0,1,0,0]] → 0（障碍阻断向右延伸，无法到达最右格）
[[0,1],[0,0]] → 1（示例 2，必须绕开第一行障碍）