不同路径 II 图解题解

这道题到底在问什么

网格

0 0 0 / 0 1 0 / 0 0 0

输出

2

最优解：一步一步想明白

1. 3最直接的想法是从起点递归，每格往右、往下各试一次，数到终点的路径条数。可同一个格子会被无数条前缀重复访问，「从这格到终点有几条路」被反复重算，网格一大就指数爆炸。
2. 4转折：用 dp[i][j] 记「走到这格有几条路」，每格只算一次。一个格子只能从上面或左边来，所以 dp[i][j] = dp[i−1][j] + dp[i][j−1]。遇到障碍，谁也站不上去，dp 直接置 0——它就不会再把路径数传给右边和下边，那些经过障碍的路自动被掐断。
3. 5起点 1 条路建一张 3×3 的 dp 表，行列数全程不变。起点不是障碍，站在那儿本身就算 1 条路，先填 dp[0][0]=1。其余先空着，按从上到下、从左到右逐格填。
4. 6无障碍 → 全 1第一行头顶没有格子，只能一路向右走过来。这一行没障碍，所以全是 1，就是一条直路。
5. 7无障碍 → 全 1第一列同理，只能一路向下，也没障碍，也全是 1。现在边界铺好了，开始填中间。
6. 8此路不通 → 清零轮到正中央，它是障碍。这里走障碍分支：不算上+左，直接把 dp 记成 0——没有任何走法能合法停在障碍上。这个 0 待会儿会传给它右边和下边。
7. 9= 1 + 0 = 1这格不是障碍，正常算上+左：上面是 1，左边是障碍传来的 0，相加只剩 1 条路。障碍的 0 在这里第一次起作用，把原本能从左边来的路抹掉了。
8. 10= 0 + 1 = 1这格也算上+左：上面又是障碍传来的 0，左边是 1，结果 1 条路。可以看到障碍的 0 同时切断了右边和下边两个方向。
9. 11dp[2][2] = 1 + 1 = 2终点 = 上面 1 + 左边 1 = 2。这正是绕过中央障碍的那 2 条路：贴上边绕一条、贴下边绕一条。
10. 12dp[2][2] = 2右下角 dp[2][2] = 2 就是答案。整张表填完，障碍那格的 0 把所有穿过它的路都拦住了。
11. 15网格 DP 里碰到不可用的格子，把它的 dp 置 0（计数题）或置无穷（最值题），它就不会再把值传给右边、下边——障碍、陷阱、禁区都这么处理。
12. 17grid[0][0]=1 → 答案 0把起点换成障碍试一下：dp[0][0] 一开始就该是 0，不能写 1。0 一路向右、向下传，整张表全是 0，最后答案是 0。这就是为什么必须先特判起点。
13. 21把这题练到能复述后，去网格 DP 专题里迁移：状态定义照搬，只改边界和「障碍清零」这一笔。卡住就问问 AI 助教，或进通关训练实战一遍。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def uniquePathsWithObstacles(self, grid):
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        if grid[0][0] == 1: return 0
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    dp[i][j] = 0
                    continue
                if i: dp[i][j] += dp[i - 1][j]
                if j: dp[i][j] += dp[i][j - 1]
        return dp[m - 1][n - 1]

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        if (grid[0][0] == 1) return 0;
        dp[0][0] = 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { dp[i][j] = 0; continue; }
                if (i) dp[i][j] += dp[i - 1][j];
                if (j) dp[i][j] += dp[i][j - 1];
            }
        return dp[m - 1][n - 1];
    }
};

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        if (grid[0][0] == 1) return 0;
        dp[0][0] = 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                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]*n for _ in range(m)]
if 起点不可用: return 0          # 先特判起点
dp[0][0] = 起点初值
for i in range(m):
    for j in range(n):
        if 不可用(i, j):            # 障碍清零跳过
            dp[i][j] = 0; continue
        if i: dp[i][j] += dp[i-1][j]  # 上
        if j: dp[i][j] += dp[i][j-1]  # 左
return dp[m-1][n-1]

// 网格DP带障碍骨架
vector<vector<int>> dp(m, vector<int>(n, 0));
if (起点不可用) return 0;          // 先特判起点
dp[0][0] = 起点初值;
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++) {
        if (不可用(i, j)) { dp[i][j] = 0; continue; }
        if (i) dp[i][j] += dp[i-1][j];  // 上
        if (j) dp[i][j] += dp[i][j-1];  // 左
    }
return dp[m-1][n-1];

// 网格DP带障碍骨架
int[][] dp = new int[m][n];
if (起点不可用) return 0;          // 先特判起点
dp[0][0] = 起点初值;
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++) {
        if (不可用(i, j)) { 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];

复杂度

面试官可能追问