leetcode 63题 代码内有链接

leetcode63.js

/**
 * from https://leetcode.com/problems/unique-paths-ii/
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
  const m = obstacleGrid.length,
    n = obstacleGrid[0].length;
  const dp = Array(m);
  for (let i = 0; i < m; i++) dp[i] = Array(n);

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const prevI = i - 1;
      const prevJ = j - 1;
      let sum = i === 0 && j === 0 ? 1 : 0;
      if (prevI >= 0 && !obstacleGrid[prevI][j]) {
        sum += dp[prevI][j];
      }
      if (prevJ >= 0 && !obstacleGrid[i][prevJ]) {
        sum += dp[i][prevJ];
      }
      dp[i][j] = sum;
      if (obstacleGrid[i][j]) {
        dp[i][j] = 0;
      }
    }
  }

  return dp[m - 1][n - 1];
};