LeetCode 题解：63. 不同路径 II，动态规划（空间 O(n)），JavaScript，详细注释

2024-06-20
福建
本文字数：778 字
阅读完需：约 3 分钟

原题链接：https://leetcode-cn.com/problems/unique-paths-ii/

解题思路：

在网格中的任意一点，都有向右和向下两种路径。同时它也是从上方和左方两个位置走过来的。
那么，任意一点的路径数量，等于从起点走到上方和左方点的数量之和。
第一行和第一列都只有一种路径，就是从起点一直走到底。
我们可以用一个二维数组，画出网格中每个点的路径数量，一直递推到终点，终点存储的就是所有的路径数量。
因此动态规划的状态转移方程为：dp[i][j]=dp[i-1][j]+dp[i][j-1]。
如果遇到障碍物，则该位置的路径数量为 0。
对于起始点obstacleGrid[0][0]，如果它没有障碍物，路径为 1，反之为 0。
由于每个点的路径数量只和它左方和上方有关，因此状态转移方程可以优化为：dp[i] = dp[i - 1] + dp[i]。

/** * @param {number[][]} obstacleGrid * @return {number} */var uniquePathsWithObstacles = function(obstacleGrid) {  // 创建数组，存储最新一行的状态  // 由于新位置的状态，只与它左方和上方的状态有关  // 也就是dp[j] = dp[j - 1] + dp[j]  // 因此只需要一维数组即可  let dp = new Array(obstacleGrid[0].length).fill(0)  // 起始位置如果无障碍物，路径为1，否则为0  dp[0] = obstacleGrid[0][0] ? 0 : 1
  // 遍历每个网格位置，计算路径数量  for (let i = 0; i < obstacleGrid.length; i++) {    for (let j = 0; j < obstacleGrid[0].length; j++) {      // 如果遇到障碍物，当前位置无法经过，路径为0      if (obstacleGrid[i][j]) {        dp[j] = 0      } else {        // 如果当前位置没有障碍物，路径数量等于左方和上方的数量之和        // 如果j为0，dp[j - 1]为undefined，将其设置为0，方便计算        dp[j] += dp[j - 1] ?? 0      }    }  }
  // 最后一个位置存储的就是最终结果  return dp[obstacleGrid[0].length - 1]};