问题

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示

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

示例 2：
leetcode-63：不同路径Ⅱ - 图2

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

思路

leetcode-62：不同路径中已经详细分析了没有障碍的情况，有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值0就可以了

动规五部曲：

  • 确定dp数组以及下标的含义

    • dp[i][j] ：表示从(0, 0)出发，到(i, j)有dp[i][j]条不同的路径

  • 确定递推公式

    • dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    • 但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）
      1. if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候，再推导dp[i][j]
      2. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      3. }

  • dp数组如何初始化 ```java int[][] dp = new int[n][n]; // 初始值为0 for(int i = 0; i < m; i++){ for(int j = 0; j< n; j++){

    1.   dp[i][j] = 0;

    } }

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

  1. 但如果`(i, 0)`这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的`dp[i][0]`应该还是初始值0<br />![640 (2).png](https://cdn.nlark.com/yuque/0/2021/png/463136/1624879874794-97c41f50-98d2-428a-8a08-830fceb3d86b.png#clientId=u437b52c6-ebe1-4&from=ui&id=ub8bbc210&margin=%5Bobject%20Object%5D&name=640%20%282%29.png&originHeight=330&originWidth=802&originalType=binary&ratio=2&size=24072&status=done&style=none&taskId=ub86a8f18-3221-41df-91d8-a85789d7b7d)
  2. ```java
  3. int[][] dp = new int[m][n];
  4. for(int i = 0; i < m; i++){
  5.     for(int j = 0; j< n; j++){
  6.         dp[i][j] = 0;
  7.     }
  8. }
  10. for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) 
  11.     dp[i][0] = 1;
  12. for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) 
  13.     dp[0][j] = 1;
  15. 注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作

  • 确定遍历顺序

    • 从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]中可以看出，一定是从左到右一层一层遍历，这样保证推导dp[i][j]的时候，dp[i - 1][j]和dp[i][j - 1]一定是有数值
      1. for (int i = 1; i < m; i++) {
      2. for (int j = 1; j < n; j++) {
      3.    if (obstacleGrid[i][j] == 1) 
      4.        continue;
      5.    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      6. }
      7. }

  • 举例推导dp数组

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int m = obstacleGrid.length;
  4.         int n = obstacleGrid[0].length;
  6.         int[][] dp = new int[m][n];
  7.         for(int i = 0; i < m; i++){
  8.             for(int j = 0; j< n; j++){
  9.                 dp[i][j] = 0;
  10.             }
  11.         }
  13.         for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) 
  14.             dp[i][0] = 1;
  15.         for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) 
  16.             dp[0][j] = 1;
  18.         for (int i = 1; i < m; i++) {
  19.             for (int j = 1; j < n; j++) {
  20.                 if (obstacleGrid[i][j] == 1) 
  21.                     continue;
  22.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  23.             }
  24.         }
  25.         return dp[m - 1][n - 1];
  26.     }
  27. }
  • 时间复杂度：leetcode-63：不同路径Ⅱ - 图3 n，m 分别为obstacleGrid 长度和宽度
  • 空间复杂度：leetcode-63：不同路径Ⅱ - 图4