63. Unique Paths II
你有一個 m x n 的整數陣列 grid。一個機器人最初位於左上角（即 grid[0][0]）。機器人試圖移動到右下角（即 grid[m - 1][n - 1]）。機器人只能在任何時候向下或向右移動。
在 grid 中，障礙物和空格分別標記為 1 或 0。機器人所走的路徑不能包含任何作為障礙物的方格。
返回機器人到達右下角的唯一路徑數。
測試用例生成的答案將小於或等於 2 * 10^9。
範例 1：
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 輸出：2 解釋：在上面的 3x3 網格中間有一個障礙物。 有兩種方法到達右下角：
- 右 -> 右 -> 下 -> 下
- 下 -> 下 -> 右 -> 右
Python
from typing import List
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m, n = len(obstacleGrid), len(obstacleGrid[0])
# If the starting point or the ending point is an obstacle, return 0
if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
return 0
# Initialize the dp array
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
# Fill the first row
for j in range(1, n):
dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0
# Fill the first column
for i in range(1, m):
dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0
# Fill the rest of the dp array
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
else:
dp[i][j] = 0
return dp[m-1][n-1]
16.51MB, 38ms
C++
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
// If the starting point or the ending point is an obstacle, return 0
if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
return 0;
}
// Initialize the dp array
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = 1;
// Fill the first row
for (int j = 1; j < n; ++j) {
dp[0][j] = (obstacleGrid[0][j] == 0) ? dp[0][j-1] : 0;
}
// Fill the first column
for (int i = 1; i < m; ++i) {
dp[i][0] = (obstacleGrid[i][0] == 0) ? dp[i-1][0] : 0;
}
// Fill the rest of the dp array
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} else {
dp[i][j] = 0;
}
}
}
return dp[m-1][n-1];
}
};
10.34MB, 5ms
Javascript
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
// If the starting point or the ending point is an obstacle, return 0
if (obstacleGrid[0][0] === 1 || obstacleGrid[m-1][n-1] === 1) {
return 0;
}
// Initialize the dp array
const dp = Array.from({ length: m }, () => Array(n).fill(0));
dp[0][0] = 1;
// Fill the first row
for (let j = 1; j < n; j++) {
dp[0][j] = obstacleGrid[0][j] === 0 ? dp[0][j-1] : 0;
}
// Fill the first column
for (let i = 1; i < m; i++) {
dp[i][0] = obstacleGrid[i][0] === 0 ? dp[i-1][0] : 0;
}
// Fill the rest of the dp array
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (obstacleGrid[i][j] === 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} else {
dp[i][j] = 0;
}
}
}
return dp[m-1][n-1];
};
49.32MB, 51ms
