63. 不同路径 II
题目描述
输入一个 m x n 的网格 obstacleGrid，格子里的 1 表示障碍，0 表示可以通行。
机器人从左上角 obstacleGrid[0][0] 出发，要走到右下角 obstacleGrid[m - 1][n - 1]。每一步只能向右或向下走一格，途经的格子（含起点和终点）都不能是障碍。
返回不同路线的数量。若起点或终点本身是障碍，答案为 0。
示例 1
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2
解释：正中间有障碍，只剩两条路：右右下下、下下右右。
示例 2
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
解释：右上角是障碍，只能先向下再向右。
数据范围
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]只会是0或1。- 保证答案不超过
2 * 10^9。
解题思路
到达格子 (i,j) 的路径数 = 从上方来的路径数 + 从左边来的路径数；障碍格的路径数为 0。只用一行数组 dp：更新前 dp[j] 是上一行同列的值（上方），dp[j-1] 已是本行左边格的值，所以 dp[j] += dp[j-1]。
为什么正确
处理完 (i,j) 后，dp[0..j] 是第 i 行的答案，dp[j+1..] 仍是第 i-1 行的答案。
复杂度分析
时间 O(mn)，空间 O(n)。
易错点
第 0 列的格子只能从上方来，不能加 dp[j-1]；但遇到障碍仍要置 0，之后整列都会是 0。起点本身是障碍时答案为 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [0] * n
dp[0] = 1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 1:
dp[j] = 0
elif j > 0:
dp[j] += dp[j - 1]
return dp[n - 1]class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else if (j > 0) {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}
}class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<long long> dp(n, 0);
dp[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else if (j > 0) {
dp[j] += dp[j - 1];
}
}
}
return (int)dp[n - 1];
}
};func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m, n := len(obstacleGrid), len(obstacleGrid[0])
dp := make([]int, n)
dp[0] = 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if obstacleGrid[i][j] == 1 {
dp[j] = 0
} else if j > 0 {
dp[j] += dp[j-1]
}
}
}
return dp[n-1]
}var uniquePathsWithObstacles = function(obstacleGrid) {
const m = obstacleGrid.length, n = obstacleGrid[0].length;
const dp = new Array(n).fill(0);
dp[0] = 1;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (obstacleGrid[i][j] === 1) {
dp[j] = 0;
} else if (j > 0) {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
};function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
const m = obstacleGrid.length, n = obstacleGrid[0].length;
const dp = new Array<number>(n).fill(0);
dp[0] = 1;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (obstacleGrid[i][j] === 1) {
dp[j] = 0;
} else if (j > 0) {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}