一、题目内容 中等

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

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

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

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

示例1：

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

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

示例2：

3. 不同路径 II（63） - 图2 输入：obstacleGrid = [[0,1],[0,0]] 输出：1

提示：

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

    二、解题思路

    如果我们自己创建数组来记录路径，把障碍物标记成 -1 之类的数。
    那在时间复杂度上，估计是 2 倍的 m x n。所以我们试着利用给定的数组来记录路径。
  1. 我们用(i,j)表示格子的坐标。坐标向下为 x 轴，向右为 y 轴。
  2. obstacleGrid[i][j]表示走到这一格可以有多少条路径。

我们假设只有一行，我们另原点的位置，路径是 1，那么往右就都是 1。如果遇到障碍物，那么这一格开始，后面的都跟这格一样，都是 0。
我们假设只有一列的情况，和上面同理。
所以可以写出两个 for 循环

  1.   // 初始化第一列
  2.   for (let i = 1; i < x; i++) {
  3.     if (obstacleGrid[i][0]) {
  4.       obstacleGrid[i][0] = 0
  5.     } else {
  6.       obstacleGrid[i][0] = obstacleGrid[i - 1][0]
  7.     }
  8.   }
  9.   // 初始化第一列
  10.   for (let i = 1; i < y; i++) {
  11.     if (obstacleGrid[0][i]) {
  12.       obstacleGrid[0][i] = 0
  13.     } else {
  14.       obstacleGrid[0][i] = obstacleGrid[0][i - 1];
  15.     }
  16.   }

接下来，开始遍历每个格子，记录每个格子的路径。我们都知道机器人是向右下方走的。
所以每个格子的路径 = 该格上面的格子路径 + 该格左边的格子路径。
如果遇到的格子obstacleGrid[i][j] === 1，说明该格存在障碍，直接置为 0 。那么别的格子利用它计算路径时，拿到 0，相当于这条路被切断了。
注意：机器人开始的位置，还有可能被放障碍物，永远是 0。这极端条件真的牛逼

三、具体代码

  1. /**
  2.  * @param {number[][]} obstacleGrid
  3.  * @return {number}
  4.  */
  5. var uniquePathsWithObstacles = function (obstacleGrid) {
  6.   // 在原点，机器人开始的位置，还放障碍，真的牛逼
  7.   if (obstacleGrid[0][0]) return 0;
  8.   const y = obstacleGrid[0].length;
  9.   const x = obstacleGrid.length;
  10.   obstacleGrid[0][0] = 1; // 初始化第一格
  11.   // 初始化第一列
  12.   for (let i = 1; i < x; i++) {
  13.     if (obstacleGrid[i][0]) {
  14.       obstacleGrid[i][0] = 0
  15.     } else {
  16.       obstacleGrid[i][0] = obstacleGrid[i - 1][0]
  17.     }
  18.   }
  19.   // 初始化第一列
  20.   for (let i = 1; i < y; i++) {
  21.     if (obstacleGrid[0][i]) {
  22.       obstacleGrid[0][i] = 0
  23.     } else {
  24.       obstacleGrid[0][i] = obstacleGrid[0][i - 1];
  25.     }
  26.   }
  27.   // 开始动态规划
  28.   for (let i = 1; i < x; i++) {
  29.     for (let j = 1; j < y; j++) {
  30.       // 如果遇到障碍，那么这一格置为 0
  31.       if (obstacleGrid[i][j]) {
  32.         obstacleGrid[i][j] = 0
  33.       } else {
  34.         // 如果没遇到障碍，那么这一格的路径 = 上面的格子路径 + 左边的格子路径
  35.         obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
  36.       }
  37.     }
  38.   }
  39.   return obstacleGrid[x - 1][y - 1];
  40. };

四、其他解法