63.不同路径II

链接：63.不同路径II
难度：Medium
标签：数组、动态规划、矩阵
简介：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

题解 1 - typescript

• 编辑时间：2020-07-06
• 执行用时：80ms
• 内存消耗：37MB
• 编程语言：typescript
• 解法介绍：dp[i][j] = dp[i+1][j] + dp[i][j+1]。

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const n = obstacleGrid.length;
  if (n === 0) return 0;
  const m = obstacleGrid[0].length;
  if (m === 0) return 0;
  else if (obstacleGrid[0][0] === 1) return 0;
  else if (n === 1) {
    for (const num of obstacleGrid[0]) if (num === 1) return 0;
    return 1;
  } else if (m === 1) {
    for (let i = 0; i < n; i++) if (obstacleGrid[i][0] === 1) return 0;
    return 1;
  } else if (obstacleGrid[n - 1][m - 1] === 1) return 0;
  else {
    const dp = new Array(n).fill(0).map(_ => new Array(m).fill(0));
    dp[n - 1][m - 2] = obstacleGrid[n - 1][m - 2] ^ 1;
    dp[n - 2][m - 1] = obstacleGrid[n - 2][m - 1] ^ 1;
    for (let i = n - 1; i >= 0; i--) {
      for (let j = m - 1; j >= 0; j--) {
        if (obstacleGrid[i][j] === 1 || dp[i][j] === 1) continue;
        dp[i][j] = (j + 1 < m ? dp[i][j + 1] : 0) + (i + 1 < n ? (dp[i][j] += dp[i + 1][j]) : 0);
      }
    }
    return dp[0][0];
  }
}