不同路径II（ LeetCode 63 ）
一、题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
现在考虑网格中有障碍物。问总共有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 不同路径II（ LeetCode 63 ）：https://leetcode-cn.com/problems/unique-paths-ii/
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
// dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
// dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
// dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
// dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
// m 行
int m = obstacleGrid.length;
// n 列
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
// i 从 1 遍历到 m - 1
// 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
// 由于每次只能向下或者向右移动一步，此时只能向下移动一步
// 所以，只能一直向下走，只有这一条路径
for(int i = 0; i < m ; i++){
// 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if(obstacleGrid[i][0] == 1) break;
// 仅此一条，别无分路
dp[i][0] = 1;
}
// j 从 1 遍历到 n - 1
// 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
// 由于每次只能向下或者向右移动一步，此时只能向右移动一步
// 所以，只能一直向右走，只有这一条路径
for(int j = 0; j < n ; j++){
// 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if(obstacleGrid[0][j] == 1) break;
// 仅此一条，别无分路
dp[0][j] = 1;
}
// 接下来从第 1 行到第 m - 1 行
// 从第 1 列到 n - 1 列
// 填充二维数组 dp 里面的值
// dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 由于每次只能向下或者向右移动一步
// 如果此时出现了障碍，那么由于无法到达这个位置，因此不用处理
if (obstacleGrid[i][j] == 1) continue;
// 位置 (i,j) 的不同路径的数量是由
// 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
// 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
// 两者之和获取到的
dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ];
}
}
// dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
// 即到达终点的数量
// 返回这个结果即可
return dp[ m - 1 ][ n - 1 ];
}
}
2、C++ 代码
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
// 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
// dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
// dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
// dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
// dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
// m 行
int m = obstacleGrid.size();
// n 列
int n = obstacleGrid[0].size();
auto dp = vector < vector < int>> ( m ,vector<int> ( n));
// i 从 1 遍历到 m - 1
// 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
// 由于每次只能向下或者向右移动一步，此时只能向下移动一步
// 所以，只能一直向下走，只有这一条路径
for(int i = 0; i < m ; i++){
// 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if(obstacleGrid[i][0] == 1) break;
// 仅此一条，别无分路
dp[i][0] = 1;
}
// j 从 1 遍历到 n - 1
// 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
// 由于每次只能向下或者向右移动一步，此时只能向右移动一步
// 所以，只能一直向右走，只有这一条路径
for(int j = 0; j < n ; j++){
// 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if(obstacleGrid[0][j] == 1) break;
// 仅此一条，别无分路
dp[0][j] = 1;
}
// 接下来从第 1 行到第 m - 1 行
// 从第 1 列到 n - 1 列
// 填充二维数组 dp 里面的值
// dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 由于每次只能向下或者向右移动一步
// 如果此时出现了障碍，那么由于无法到达这个位置，因此不用处理
if (obstacleGrid[i][j] == 1) continue;
// 位置 (i,j) 的不同路径的数量是由
// 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
// 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
// 两者之和获取到的
dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ];
}
}
// dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
// 即到达终点的数量
// 返回这个结果即可
return dp[ m - 1 ][ n - 1 ];
}
};
3、Python 代码
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
# 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
# dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
# dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
# dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
# dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
# m 行
m = len(obstacleGrid)
# n 列
n = len(obstacleGrid[0])
dp = [[0] * n for _ in range(m)]
# i 从 0 遍历到 m - 1
# 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
# 由于每次只能向下或者向右移动一步，此时只能向下移动一步
# 所以，只能一直向下走，只有这一条路径
for i in range( 0 , m ):
# 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if obstacleGrid[i][0] == 1 : break
# 仅此一条，别无分路
dp[i][0] = 1
# j 从 0 遍历到 n - 1
# 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
# 由于每次只能向下或者向右移动一步，此时只能向右移动一步
# 所以，只能一直向右走，只有这一条路径
for j in range( 0 , n ):
# 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if obstacleGrid[0][j] == 1 : break
# 仅此一条，别无分路
dp[0][j] = 1
# 接下来从第 1 行到第 m - 1 行
# 从第 1 列到 n - 1 列
# 填充二维数组 dp 里面的值
# dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
for i in range( 1 , m ):
for j in range( 1 , n ):
# 由于每次只能向下或者向右移动一步
# 如果此时出现了障碍，那么由于无法到达这个位置，因此不用处理
if obstacleGrid[i][j] == 1 : continue
# 位置 (i,j) 的不同路径的数量是由
# 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
# 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
# 两者之和获取到的
dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ]
# dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
# 即到达终点的数量
# 返回这个结果即可
return dp[ m - 1 ][ n - 1 ]
四、动画理解（没有声音）
隐藏内容
此处内容需要权限查看
