LeetCode 题解：63. 不同路径 II，动态规划，JavaScript，详细注释

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

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

解题思路：

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

/** * @param {number[][]} obstacleGrid * @return {number} */var uniquePathsWithObstacles = function(obstacleGrid) {  const m = obstacleGrid.length // 缓存行数  const n = obstacleGrid[0].length // 缓存列数
  // 如果起点和终点有障碍物，则没有路径，返回0  if (obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1]) {    return 0  }
  // 创建m行n列数组缓存结果  let dp = Array.from({ length: m }, () => new Array(n).fill(0))  let canGoDown = true // 用于判断第一列是否可以继续向下走  let canGoRight = true // 用于判断第一行是否可以继续向下走
  // 初始化第一列，如果遇到障碍物，表示从障碍物开始，不可以继续往下走，路径都为0  for (let i = 0; i < m; i++) {    if (obstacleGrid[i][0]) {      canGoDown = false    }    if (canGoDown) {      dp[i][0] = 1    }  }
  // 初始化第一行，如果遇到障碍物，表示从障碍物开始，不可以继续往下走，路径都为0  for (let i = 0; i < n; i++) {    if (obstacleGrid[0][i]) {      canGoRight = false    }    if (canGoRight) {      dp[0][i] = 1    }  }
  // 从第二行第二列开始完成递推，遇到障碍物的位置，路径为0  for (let i = 1; i < m; i++) {    for (let j = 1; j < n; j++) {      if (!obstacleGrid[i][j]) {        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]      }    }  }
  // 网格的最后一位为结果  return dp[m - 1][n - 1]};