leetCode/63.不同路径II.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>62. 不同路径</title>
  </head>
  <body>
    <script>
      // 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

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

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

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

      /**
       * @param {number[][]} obstacleGrid
       * @return {number}
       */
      var uniquePathsWithObstacles = function (obstacleGrid) {};

      let obstacleGrid = [
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]
      ];
      let res = 2;

      // 解释：
      // 3x3 网格的正中间有一个障碍物。
      // 从左上角到右下角一共有 2 条不同的路径：
      // 1. 向右 -> 向右 -> 向下 -> 向下
      // 2. 向下 -> 向下 -> 向右 -> 向右

      // obstacleGrid = [
      //   [0, 1],
      //   [0, 0]
      // ];
      // res = 1;

      // obstacleGrid = [[1, 0]];
      // res = 0;

      // 动态规划

      var uniquePathsWithObstacles = function (obstacleGrid) {
        const n = obstacleGrid.length;
        const m = obstacleGrid[0].length;

        const dp = new Array(m).fill(0);
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

        for (let i = 0; i < n; i++) {
          for (let j = 0; j < m; j++) {
            if (obstacleGrid[i][j] == 1) {
              dp[j] = 0;
              continue;
            }
            if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
              dp[j] += dp[j - 1];
            }
          }
        }

        return dp[m - 1];
      };

      obstacleGrid = [[0, 0]];

      console.log(`res: ${res} === `, uniquePathsWithObstacles(obstacleGrid));
    </script>
  </body>
</html>