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

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

解题思路:

  1. 在网格中的任意一点,都有向右和向下两种路径。同时它也是从上方和左方两个位置走过来的。
  2. 那么,任意一点的路径数量,等于从起点走到上方和左方点的数量之和。
  3. 第一行和第一列都只有一种路径,就是从起点一直走到底。
  4. 我们可以用一个二维数组,画出网格中每个点的路径数量,一直递推到终点,终点存储的就是所有的路径数量。
  5. 因此动态规划的状态转移方程为:dp[i][j]=dp[i-1][j]+dp[i][j-1]。
  6. 如果遇到障碍物,则该位置的路径数量为0。
  7. 对于起始点obstacleGrid[0][0],如果它没有障碍物,路径为1,反之为0。
  8. 由于每个点的路径数量只和它左方和上方有关,因此状态转移方程可以优化为: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]
};
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容