FatGod Blog
搜索 K

Appearance

🤖 不同路径 II ​

📝 题目描述 ​

​ 一个机器人位于一个m x n网格obstacleGrid的左上角（起点在下图中标记为Start）。机器人每次只能向下或者向右移动一步。机器人试图到达网格的右下角（终点在下图中标记为Finish）。

​ 现在考虑网格中有障碍物，障碍物的数量count区间为count >= 0。网格中的障碍物和空位置分别用数字1和0表示。

有障碍的网格

​ 请你计算出机器人从起点到达终点共有多少条不同的路径。需要说明的是，1 x 1的无障碍网格的路径数取值为1，且障碍物存在于起点或终点的网格的路径数取值为0。

📋 代码模版 ​

java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

    }
}
typescript
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    
}

💡 提示 ​

  1. 1≤m≤100
  2. 1≤n≤100
  3. obstacleGrid[i][j] 为 0 或 1

🚀 示例 ​

示例一 ​

​ obstacleGrid输入为[[0,0,0],[0,1,0],[0,0,0]]，这是一个3 x 3的网格，示意图如下。

示例一

​ 在该网格上，机器人从起点到达终点的路径共有2条。

  1. 向右 → 向右 → 向下 → 向下

示例一走法①

  1. 向下→ 向下 → 向右 → 向右

示例一走法②

示例二 ​

​ obstacleGrid输入为[[0,0,1,0,0],[0,1,0,0,0],[0,0,0,1,0],[0,1,0,0,0]]，这是一个4 x 5的网格，示意图如下。

示例二

​ 在该网格上，机器人从起点到达终点的路径只有1条。

  1. 向下→ 向下 → 向右 → 向右 → 向下 → 向右 → 向右

示例二走法①

示例三 ​

​ obstacleGrid输入为[[0,1,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]，这是一个6 x 9的网格，示意图如下。

示例三

​ 在该网格上，机器人从起点到达终点的路径不存在，即0条。

🖊️ 题解 ​

​ 本题是题目不同路径的进阶版，因此在解决这道题之前，强烈建议先处理题目不同路径。两者唯一的区别为：本题的网格中可能存在障碍物，而题目不同路径的网格中肯定没有障碍物。下面我们来探讨下障碍物对机器人在网格中移动产生的影响。

​ 在题目不同路径中，当计算到达当前格子的路径总数时，我们会先计算到达其上边和左边的格子的路径总数。但在本题中，如果这两个相龄的格子中出现障碍物，障碍物将阻挡机器人向下或向右移动。因此，当计算的格子中出现障碍物时，其路径总数直接返回 0。

到达当前格子的两种走法

​ 在题目不同路径中，边界条件为网格第一行和第一列上的格子，它们的路径总数为 1。但在本题中，对于第一行与第一列中的元素，如果它前面（上面）存在障碍物，那么其对应的路径总数为 0。

第一行和第一列上的唯一路径

​ 需要说明的是，在本题中，网格的行与列的索引从0开始，即最上面一行索引为0，最左边一列索引为0。同时，重设 m=obstacleGrid.length−1，n=obstacleGrid[0].length−1。

记忆化搜索 ​

​ 本题中使用的记忆化深度优先遍历dfs的递归公式与题目不同路径相同，即dfs(i,j)=dfs(i−1,j)+dfs(i,j−1)，其中 dfs(i,j) 为⭐️机器人到达格子 (i,j) 的路径总数⭐️，并且0≤i≤m,0≤j≤n。递归边界条件较为复杂，如果obstacleGrid[i][j]=1，则 dfs(i,j)=0，如果 i=0 或 j=0，则判断对应格子前面（上面）是否存在障碍物，若存在，那么dfs(i,j)=0，反之 dfs(i,j)=1。为了进一步优化算法效率，我们可以提前遍历网格的第一行和第一列，将每个格子的路径总数结果存储在记忆化数组中。

java
class Solution {
    private final static int NOT_CALC = -1;

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length - 1;
        int n = obstacleGrid[0].length - 1;
        int[][] memory = new int[m + 1][n + 1];
        for (int[] arr : memory) {
            Arrays.fill(arr, NOT_CALC);
        }
        memory[0][0] = obstacleGrid[0][0] ^ 1;
        for (int i = 1; i <= n; i++) {
            memory[0][i] = obstacleGrid[0][i] == 1 ? 0 : memory[0][i - 1];
        }
        for (int i = 1; i <= m; i++) {
            memory[i][0] = obstacleGrid[i][0] == 1 ? 0 : memory[i - 1][0];
        }
        return dfs(m, n, obstacleGrid, memory);
    }

    private int dfs(int i, int j, int[][] obstacleGrid, int[][] memory) {
        if (obstacleGrid[i][j] == 1) {
            return 0;
        }
        if (memory[i][j] != NOT_CALC) {
            return memory[i][j];
        }
        return memory[i][j] = dfs(i - 1, j, obstacleGrid, memory) +
                dfs(i, j - 1, obstacleGrid, memory);
    }
}
typescript
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length - 1, n = obstacleGrid[0].length - 1;
    const memory: number[][] = Array.from({ length: m + 1 }, () => []);
    memory[0][0] = obstacleGrid[0][0] ^ 1;
    for (let i = 1; i <= n; i++) {
        memory[0][i] = obstacleGrid[0][i] == 1 ? 0 : memory[0][i - 1];
    }
    for (let i = 1; i <= m; i++) {
        memory[i][0] = obstacleGrid[i][0] == 1 ? 0 : memory[i - 1][0];
    }
    const dfs = (i: number, j: number): number => {
        if (obstacleGrid[i][j] == 1) {
            return 0;
        }
        if (memory[i][j] !== undefined) {
            return memory[i][j];
        }
        return memory[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
    }
    return dfs(m, n);
}

动态规划 ​

普通版 ​

java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length - 1;
        int n = obstacleGrid[0].length - 1;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = obstacleGrid[0][0] ^ 1;
        for (int i = 1; i <= n; i++) {
            dp[0][i] = obstacleGrid[0][i] == 1 ? 0 : dp[0][i - 1];
        }
        for (int i = 1; i <= m; i++) {
            dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : (dp[i - 1][j] + dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
}
typescript
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length - 1, n = obstacleGrid[0].length - 1;
    const dp: number[][] = Array.from({ length: m + 1 }, () => []);
    dp[0][0] = obstacleGrid[0][0] ^ 1;
    for (let i = 1; i <= n; i++) {
        dp[0][i] = obstacleGrid[0][i] == 1 ? 0 : dp[0][i - 1];
    }
    for (let i = 1; i <= m; i++) {
        dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m][n];
}

状态压缩版 ​

java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length - 1;
        int n = obstacleGrid[0].length - 1;
        int[] cur = new int[n + 1];
        cur[0] = obstacleGrid[0][0] ^ 1;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    cur[j] = 0;
                } else {
                    cur[j] += j - 1 >= 0 ? cur[j - 1] : 0;
                }
            }
        }
        return cur[n];
    }
}
typescript
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length - 1, n = obstacleGrid[0].length - 1;
    const cur: number[] = Array(n + 1).fill(0);
    cur[0] = obstacleGrid[0][0] ^ 1;
    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            if (obstacleGrid[i][j] == 1) {
                cur[j] = 0;
            } else {
                cur[j] += j - 1 >= 0 ? cur[j - 1] : 0;
            }
        }
    }
    return cur[n];
}

💭 复杂度分析 ​

​ 基于记忆化搜索的解决方案的复杂度分析如下。

  • 时间复杂度：O(mn)。
  • 空间复杂度：O(mn) 。

​ 基于动态规划的最优（状态压缩）解决方案的复杂度分析如下。

  • 时间复杂度：O(mn)。
  • 空间复杂度：O(n) 。

上次更新于: