不同路径2 中等🌟🌟🌟🌟
问题描述
原文链接：63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]为0或1
代码实现
Java
class Solution {
/*
第一步：
dp[i][j]:表示走到（i，j）这个地方一共有 dp[i][j]条路径
第二步：找关系式
if(obstacleGrid[i][j] == 1){
dp[i][j] = 0
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
第三步：初始值
dp[0][0] = obstacleGrid[0][0] == 1? 0 : 1;
dp[0][j] = dp[0][j-1]
dp[i][0] = dp[i-1][0];
*/
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
int[][] dp = new int[n][m];
dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
// 最上面一行
for(int j = 1; j < m; j++){
dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1];
}
// 最左边一列
for(int i = 1; i < n; i++){
dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0];
}
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
if(obstacleGrid[i][j] == 1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[n-1][m-1];
}
}
Python
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
"""
第一步：
dp[i][j]:表示走到（i，j）这个地方一共有 dp[i][j] 条路径
第二步：找关系式
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
第三步：初始值
dp[0][0] = 0 if obstacleGrid[0][0] == 1 else 1
dp[0][j] = dp[0][j-1]
dp[i][0] = dp[i-1][0]
"""
n = len(obstacleGrid)
m = len(obstacleGrid[0])
dp = [[0 for _ in range(m)] for _ in range(n)]
dp[0][0] = 0 if obstacleGrid[0][0] == 1 else 1
# 最上面一行
for j in range(1, m):
dp[0][j] = 0 if obstacleGrid[0][j] == 1 else dp[0][j-1]
# 最左边一列
for i in range(1, n):
dp[i][0] = 0 if obstacleGrid[i][0] == 1 else dp[i-1][0]
for i in range(1, n):
for j in range(1, m):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n-1][m-1]
C++
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
/*
第一步：
dp[i][j]:表示走到（i，j）这个地方一共有 dp[i][j] 条路径
第二步：找关系式
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
第三步：初始值
dp[0][0] = 0 if obstacleGrid[0][0] == 1 else 1
dp[0][j] = dp[0][j-1]
dp[i][0] = dp[i-1][0]
*/
int n = obstacleGrid.size();
int m = obstacleGrid[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
dp[0][0] = (obstacleGrid[0][0] == 1) ? 0 : 1;
// 最上面一行
for (int j = 1; j < m; j++) {
dp[0][j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0][j-1];
}
// 最左边一列
for (int i = 1; i < n; i++) {
dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i-1][0];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[n-1][m-1];
}
};
Go
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
/*
第一步：
dp[i][j]:表示走到（i，j）这个地方一共有 dp[i][j] 条路径
第二步：找关系式
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
第三步：初始值
dp[0][0] = 0 if obstacleGrid[0][0] == 1 else 1
dp[0][j] = dp[0][j-1]
dp[i][0] = dp[i-1][0]
*/
n := len(obstacleGrid)
m := len(obstacleGrid[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
dp[0][0] = 0
if obstacleGrid[0][0] == 0 {
dp[0][0] = 1
}
// 最上面一行
for j := 1; j < m; j++ {
dp[0][j] = 0
if obstacleGrid[0][j] == 0 {
dp[0][j] = dp[0][j-1]
}
}
// 最左边一列
for i := 1; i < n; i++ {
dp[i][0] = 0
if obstacleGrid[i][0] == 0 {
dp[i][0] = dp[i-1][0]
}
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
if obstacleGrid[i][j] == 1 {
dp[i][j] = 0
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[n-1][m-1]
}