不同路径 I 、II

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径
示例：
:::info 输入：m = 3, n = 7
输出：28 :::

思路

按照动态规划五部曲来分析：

1. 首先确定 dp 数组及其下标的含义

dp[i][j]: 指的是从(0, 0) 到坐标(i, j)的路径数量。

1. 动态规划递推公式

可以确定的是，在大于第一列和第一行的坐标，只能从左边元素和上方元素到达，即左边元素和上方元素的路径数量之和，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。

1. 初始化

将第一行和第一列的所有元素路径数量均设为 1。

1. 确定遍历顺序

这里要看一下递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的

1. 举例推导数组

var uniquePaths = function(m, n) {
  // 生成二维数组时，元素直接赋值为1
  const dp = new Array(m).fill().map(() => new Array(n).fill(1));
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
  } 
  return dp[m-1][n-1];
};

但是，我们其实也可以用一维数组，直接滚动遍历即可，可以优化空间。

var uniquePaths = function(m, n) {
    const dp = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j-1];
        }
    } 
    return dp[n-1];
};

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例：
:::info 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右 :::

思路

本道题与 62.不同路径 的思路是一致的，在上一题中，我们遇到了没有障碍物的情况，而在这道题职工，当我们遇到障碍物时，我们可以设置该元素坐标对应的dp为 0 即可。
但是，值得注意的一点是，在初始化过程中，如果第一行或第一列的某个元素为障碍物，则其后面的元素均不能到达，即为 0 。

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = new Array(m).fill().map(() => new Array(n).fill(0));
    // 初始化
    for (let i = 0; i < m && obstacleGrid[i][0] === 0; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n && obstacleGrid[0][j] === 0; j++) {
        dp[0][j] = 1;
    }
    // 递归公式
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
          // 如果当前元素为障碍物，直接将其设置为 0 
            dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i-1][j] + dp[i][j-1]; 
        }
    }
    return dp[m-1][n-1];
};