一个机器人位于一个 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

解题思路

  1. 有障碍物
    1. 主要是初始化的时候麻烦
    2. 递推过程一样
  2. 初始化障碍物的网格
    1. 第一个位置
      1. dp[0][0] = 1 ;
    2. 初始化行列
      1. 需要判断
        1. if (obstacleGrid[0][c] != 1)
        2. 如果遇到石头，走不通，用默认0
        3. 如果不是石头，就取前面的值，所以如果前面的阻塞了，后面的也都走不通
  3. 动态递推
    1. 遍历
  1. /**
  2.  * @param {number[][]} obstacleGrid
  3.  * @return {number}
  4.  */
  5. var uniquePathsWithObstacles = function (obstacleGrid) {
  6.   if (obstacleGrid[0][0] == 1) return 0; // 出发点就被障碍堵住 
  8.   const rows = obstacleGrid.length;       // 行
  9.   const cols = obstacleGrid[0].length;    // 列
  10.   // 初始化 
  11.   // map无法遍历空的，要么就要用for循环
  12.   const dp = new Array(rows).fill(0).map(() => new Array(cols).fill(0));
  14.   // base case
  15.   dp[0][0] = 1;
  17.   // 第一行
  18.   for (let c = 1; c < cols; c++) {
  19.     // 只要当前不是障碍物，值就是1
  20.     // 遇到障碍物，之后的都不会赋值为1了
  21.     if (obstacleGrid[0][c] != 1) {
  22.       dp[0][c] = dp[0][c - 1];
  23.     }
  24.   }
  25.   // 第一列
  26.   for (let r = 1; r < rows; r++) {
  27.     if (obstacleGrid[r][0] != 1) {
  28.       dp[r][0] = dp[r - 1][0];
  29.     }
  30.   }
  31.   // 动态递推
  32.   for (var r = 1; r < rows; r++) {
  33.     for (var c = 1; c < cols; c++) {
  34.       // 遇到障碍物不能走
  35.       if (obstacleGrid[r][c] != 1) {
  36.         dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
  37.       }
  38.     }
  39.   }
  40.   return dp[rows - 1][cols - 1];
  41. };