63. 不同路径 II🔖DP

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

动态规划

62. 不同路径🔖DP题目的延申。

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

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

1. 状态转移方程

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

2. 初始状态

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

1. 起点即终点
2. 起点为障碍物

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]
};