每天一道leetcode(Day 59)

63. 不同路径 II

题目描述

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

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

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

说明：m 和 n 的值均不超过 100。

示例

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

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

解题思路

解题思路：动态规划，类似63. 不同路径;

• 本地在上一题的基础上存在障碍物设置，那既然是障碍物，则说明此路不通，即经过此节点的路径数为 0，所以当遇到障碍物时，设置 dp[i][j] = 0 即可；
• 所以第一行第一列数据初始化的时候就不能都是 1 了，因为有的地方有障碍物存在；
• 初始化 dp 二维数组的时候需要看对应的 obstacleGrid 数组是否存在障碍物；这样 dp 递推的时候，只需要在 62 题的基础上加上 obstacleGrid[i][j]当前节点不为障碍物的条件即可;

代码

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
  let n = obstacleGrid.length,
    m = obstacleGrid[0].length,
    dp = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(m).fill(0);
  }
  dp[0][0] = obstacleGrid[0][0] === 0 ? 1 : 0;
  // 如果起点就有障碍物，返回0
  if (!dp[0][0]) return 0;
  // 遍历得到第一行的值
  for (let i = 1; i < m; i++) {
    if (!obstacleGrid[0][i]) {
      dp[0][i] = dp[0][i - 1];
    }
  }
  // 遍历第一列
  for (let j = 1; j < n; j++) {
    if (!obstacleGrid[j][0]) {
      dp[j][0] = dp[j - 1][0];
    }
  }
  // 动态规划
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      if (!obstacleGrid[i][j]) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }
  return dp[n - 1][m - 1];
};

参考

63. 不同路径 II