不同路径Ⅱ

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

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

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

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

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i] [j] 为 0 或 1

动态规划

此题同62. 不同路径，只是本题有了障碍物，如果（i，j）处有障碍，那么只需将此处的dp[i] [j]置为0即可

确定dp数组及下标的含义

dp[i] [j] 表示从（0，0）出发到达（i，j）有多少条不同的路径

确定递推公式

当前位置的路径只能由上和左两个方向推出来，因为题目规定了只能向右或向下移动

dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]

但又因为本题有障碍物的限制，代码应为

if (obstacleGrid[i][j] == 0) {
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}

初始化dp数组

该问题的初始化同62. 不同路径不同，如果在（0，j）上有障碍物，那么障碍物右边都是不可到达的，同理，如果在（i，0）上有障碍物，那么障碍物的下边也是不可到达的，初始化应为

for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

如图所示

确定遍历顺序

根据推导公式，从左到右，从上到下层次遍历即可

拿实例1举例

其dp数组状态如图

代码

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        //dp[i][j]表示从(0,0)到(i,j)有几条路径
        for(int i = 0; i<m && obstacleGrid[i][0]==0; i++){ //第一列障碍物下面的都为0,表示不可达         
            dp[i][0] = 1;
        }
        for(int j = 0; j<n && obstacleGrid[0][j]==0; j++){ //第一行障碍物右边的都为0,表示不可达
            dp[0][j] = 1;
        }

        for(int i = 1; i<m ; i++){
            for(int j = 1; j<n; j++){
                if(obstacleGrid[i][j]!=1){ //没有障碍物
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

• 时间复杂度：$O(n×m)$
• 空间复杂度：$O(n×m)$