63. 不同路径 II（Unique Paths II）¶
频次 ★★★ · 难度 🟡 · 高频：美团
题目¶
m×n 网格，含障碍物（1 = 障碍），从左上到右下每次只能右或下，求路径总数。
示例：
思路¶
DP：在 62 基础上加障碍判断。dp[j] += dp[j-1] 仅当该格不是障碍。障碍物处 dp[j] = 0。
代码¶
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid[0].length;
int[] dp = new int[n];
dp[0] = 1; // 起点无障则初始为 1
for (int[] row : obstacleGrid) {
for (int j = 0; j < n; j++) {
if (row[j] == 1) {
dp[j] = 0; // 障碍物处路径数为 0
} else if (j > 0) {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}
障碍的三种写入法（计数型 DP 的"不可行"表达）¶
| 写法 | 形态 | 优劣 |
|---|---|---|
| 判零跳过（本题） | if (grid[i][j]==1) dp[i][j]=0; else 递推 |
最直白——障碍格贡献 0 条路径，邻居加它时天然斩断 |
| 初始化中断 | 首行/首列从左/上扫，遇障碍 break，后面全 0 | 显式（"断链"看得见）——62 全 1 初始化在障碍下的必要修正 |
| 减法后处理 | 先 62 全算，再减去穿障碍的路径 | 复杂化不推荐（需要扫描所有穿障碍的方案） |
起点/终点可能本身是障碍（[1]→0）：首格特判 return 0 或依赖 dp[0][0]=0 自洽（dp 判零法天然涵盖）。
复杂度¶
- 时间：O(m×n)
- 空间：O(n)
边界条件¶
- 起点或终点是障碍：返回 0
- 全无障碍：退化为 62
变式¶
易错点¶
- 起点 dp[0] 初始化为
1只有第一格非障碍时才有意义。如果起点就是障碍应该在遍历前返回 0 - 障碍物处
dp[j] = 0而不是dp[j] = dp[j-1]
面试追问¶
- 如果障碍物动态变化怎么办？ 每步重新计算？需要不同结构。一般不会问到这个程度