[NC]325. 不同路径的数目 II

🚩传送门：牛客题目
力扣题目

题目

机器人在 大小的地图的左上角（起点），每次可以 向下 或 向右 移动。要到达地图的右下角（终点）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径 ？
网格中的障碍物和空位置分别用 和 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

解题思路：动态规划

👉 定义： 来表示从坐标 到坐标 的路径总数 。

表示坐标 是否可行，如果坐标有障碍物， ，否则 。

「机器人每次只能向下或者向右移动一步」，所以从坐标 到坐标 的路径总数的值只取决于 与 的和。当坐标 本身有障碍的时候，任何路径都到到不了。

状态转移方程：

边界情况：

1. 起点和终点 有障碍物，直接返回
2. 边界 行，列，正常全部为 ，只有一种路径可达，一直向左或向下
3. 当 出现障碍物后， 列下面的全部不可达
4. 当 出现障碍物后， 行后面的全部不可达

复杂度分析

时间复杂度：，其中 为网格的行数， 为网格的列数 。

空间复杂度：，利用滚动数组优化，我们可以只用 大小来记录当前的 。

我的代码

class Solution {
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 数组空
        if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
        // 起点终点有障碍物
        if (obstacleGrid[0][0] == 1 ||obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) return 0;  
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[i].length; j++) {
                // 起点
                if (i == 0 && j == 0) {
                    dp[0][0] = 1;
                    continue;
                }
                // 0行
                if (i == 0) {
                    // 有障碍物置零,无障碍物状态从左面转移
                    if (obstacleGrid[0][j] == 1) dp[0][j] = 0;
                    else
                        dp[0][j] = dp[0][j - 1];
                    continue;
                }
                // 0列
                if (j == 0) {
                    // 有障碍物置零,无障碍物状态从上面转移
                    if (obstacleGrid[i][0] == 1) dp[i][0] = 0;
                    else
                        dp[i][0] = dp[i - 1][0];
                    continue;
                }
                // 非0行0列
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    // 无障碍物状态从上面、左面转移
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}

解题思路：深搜

备注：对于题目有时间限制的可能过不了，会显示超时

从起点开始按照 右下 两个方向深搜，遇到 终点 ，结果路径增，搜索整个地图的所有路径可能性，找出最终答案数 。

我的代码

class Solution {
    int res = 0;
    // 可行用0表示,障碍物用1表示,临时访问置1
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 非法判断
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0][0] == 1 ||
                obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1)
            return 0;
        dfs(0, 0, obstacleGrid);
        return res;
    }
    private void dfs(int i, int j, int[][] obstacleGrid) {
        // 判断边界合法性
        if (i < 0 || i >= obstacleGrid.length || j < 0 || j >= obstacleGrid[i].length) return;
        // 判断当前位置是否可行
        if (obstacleGrid[i][j] == 1) return;
        // 判断是否到达终点
        if (i == obstacleGrid.length - 1 && j == obstacleGrid[0].length - 1) {
            res++;
            return;
        }
        // 标记当前位置被访问
        obstacleGrid[i][j]=1;
        // 右下
        int[][] dir = new int[][]{{0, 1}, {1, 0}};
        for (int k = 0; k < dir.length; k++) {
            dfs(i + dir[k][0], j + dir[k][1], obstacleGrid);
        }
        // 释放当前位置的访问
        obstacleGrid[i][j]=0;
    }
}