不同路径II
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
示例 1：
codeType
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
codeType
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] 为 0 或 1
解法
ts
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
// dp[i][j]表示到达i,j的路径数量
// 只能从i-1,j 或 i,j-1到达i,j
// 所以dp[i][j] = dp[i-1][j] + dp[i][j-1]
const n = obstacleGrid.length
const m = obstacleGrid[0].length
const dp = new Array(n).fill(0).map(() => new Array(m).fill(0))
for(let i = 0; i < n; i++){
for(let j = 0; j < m; j++){
if(obstacleGrid[i][j] === 1){ // 障碍格
dp[i][j] = 0
continue
}
if(i === 0 && j === 0){ // 初始格子单独处理
dp[i][j] = 1
continue
}
let top = 0, left = 0
if(i - 1 >= 0 && obstacleGrid[i - 1][j] === 0){ // 上方可走
top = dp[i - 1][j]
}
if(j - 1 >= 0 && obstacleGrid[i][j - 1] === 0){ // 左边可走
left = dp[i][j - 1]
}
dp[i][j] = top + left
}
}
return dp[n - 1][m - 1]
};