63. 不同路径 II🔖DP

https://leetcode.cn/problems/unique-paths-ii

动态规划

这个题目的难点不是在状态转移方程的建立，而是初始状态的建立。

数据预处理说明，对障碍物或是走不通的格子都设置为0

状态转移方程

不变。和62. 不同路径🔖DP中的方程一样：f[i][j] = f[i-1][j] + f[i][j-1]

初始状态
上边界和左边界：不能单纯的全部设为1，如果有障碍物，那么后续的路（往右/往下）走不通
正式区域（非上/左边界）：遇到障碍物那么就是走不通，即0
比较特殊的初始状态：
起点即终点
起点为障碍物

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  if (obstacleGrid[0][0]) return 0
  const m = obstacleGrid.length
  const n = obstacleGrid[0].length
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const curr = obstacleGrid[i][j]
      if (!i || !j) {
        if (!i && !j) {
          obstacleGrid[i][j] = m === 1 && n === 1 ? 1 : 0
        } else if (curr || (j > 1 && obstacleGrid[0][j - 1] === 0) || (i > 1 && obstacleGrid[i - 1][0] === 0)) {
          obstacleGrid[i][j] = 0
        } else {
          obstacleGrid[i][j] = 1
        }
      } else if (curr) {
        obstacleGrid[i][j] = 0
      } else {
        obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
      }
    }
  }
  return obstacleGrid[m - 1][n - 1]
};

动态规划

树下留言