Leetcode 063 不同路径二
2024-09-07 05:50:46
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明:m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
动态规划问题,每一格的路径数都是等于它左边和上边格子的路径数目之和,其中要注意的是初始化问题,第一行和第一列都只有一种路径,但是在遍历过程中如果有障碍物,那么从这个格子开始剩下的都是0,网格中出现障碍物,那么这个格子的路径也要被置为0。
Java写法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n]; 大专栏 Leetcode 063 不同路径二for(int i=0; i<m; i++){
if(obstacleGrid[i][0]==1){
break;
}
dp[i][0]=1;
}
for(int i=0; i<n; i++){
if(obstacleGrid[0][i]==1){
break;
}
dp[0][i]=1;
} for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
if(obstacleGrid[i][j]==1){
dp[i][j]=0;
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} }
}
return dp[m-1][n-1];
}
}Python写法:
class :
def uniquePaths(self, m: int, n: int) -> int:
if not obstacleGrid:
return 0 n = len(obstacleGrid)
m = len(obstacleGrid[0]) dp = [[0 for i in range(m)] for i in range(n)] for i in range(m):
if obstacleGrid[0][i] == 1:
break
dp[0][i] = 1 for i in range(n):
if obstacleGrid[i][0] == 1:
break
dp[i][0] = 1 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]
最新文章
- Win下必备利器之Cmder
- iOS创建自定义的xib视图,不带控制器调用
- 【CSS 杂记】
- POJ 3414
- ASM:《X86汇编语言-从实模式到保护模式》5-7章:汇编基础
- python: shutil模块 -拷贝文件
- Js高程笔记->;引用类型
- Struts Convention Plugin 流程 (2.1.6+)
- Spring 注解 @Resource和@Autowired(转)
- React Native专题
- Hadoop Hive sql语法详解
- JS实现图片翻书效果
- C# 打开指定文件或网址
- mysql设置root的密码
- POJ 1995 Raising Modulo Numbers
- web前端+javascript+h5电子书籍和实战分享
- 来自projecteuler.net网站的练习题2
- linux free命令解读
- Axis1.4之即时发布服务
- linux系统下Apache日志分割(按天生成文件)