当前位置:网站首页>The unique path of leetcode topic resolution II
The unique path of leetcode topic resolution II
2022-06-12 02:29:00 【ruochen】
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0] ]
The total number of unique paths is 2.
Note: m and n will be at most 100.
When there are obstacles (obstacleGridi==1), The corresponding dp Set up 0(dpi=0).
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid[0] == null) {
return 0;
}
if (obstacleGrid[0][0] == 1) {
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int y = 1; y < n; y++) {
if (obstacleGrid[0][y] == 0) {
dp[0][y] = 1;
} else {
break;
}
}
for (int x = 1; x < m; x++) {
if (obstacleGrid[x][0] == 0) {
dp[x][0] = 1;
} else {
break;
}
}
for (int y = 1; y < n; y++) {
for (int x = 1; x < m; x++) {
if (obstacleGrid[x][y] == 1) {
dp[x][y] = 0;
} else {
dp[x][y] = dp[x - 1][y] + dp[x][y - 1];
}
}
}
return dp[m - 1][n - 1];
}边栏推荐
- Master of a famous school has been working hard for 5 years. AI has no paper. How can the tutor free range?
- Introduction to architecture - who moved my cake
- Force deduction solution summary 467- unique substring in surrounding string
- xcall 集群脚本(查看jps命令)
- 高考完不要急着去打工了,打工以后有的是机会,不差这三个月
- 力扣解法汇总905-按奇偶排序数组
- 力扣解法汇总386-字典序排数
- [adjustment] in 2022, the Key Laboratory of laser life sciences of the Ministry of education of South China Normal University enrolled adjustment students in optics, electronic information, biomedicin
- 力扣解法汇总-04.06. 后继者
- Oracle 11g graphic download installation tutorial (step by step)
猜你喜欢

程序员应该如何解决买菜难问题?手把手带你利用无障碍辅助功能快速下单抢菜

RPA introduction

How to make div 100% page (not screen) height- How to make a div 100% of page (not screen) height?

ACL 2022 - strong combination of pre training language model and graphic model

RPC 入门

Apply concentrated load to nodes in batch in ABAQUS

Layered architecture of DDD

Does the virtual host have independent IP

El upload upload file
![[adjustment] in 2022, the Key Laboratory of laser life sciences of the Ministry of education of South China Normal University enrolled adjustment students in optics, electronic information, biomedicin](/img/f9/332b206d5aca0ca6afc3fdf11a53c8.jpg)
[adjustment] in 2022, the Key Laboratory of laser life sciences of the Ministry of education of South China Normal University enrolled adjustment students in optics, electronic information, biomedicin
随机推荐
SwiftyJSON解析本地JSON文件
【无标题】2022煤矿安全检查考题及在线模拟考试
Red's deleted number
Force deduction solution summary 433- minimum gene change
程序员应该如何解决买菜难问题?手把手带你利用无障碍辅助功能快速下单抢菜
Force deduction solution summary 699- dropped blocks
El upload upload file
Almost all schools will ask for the second round exam! Come in and recite the answer!
力扣解法汇总面试题 01.05. 一次编辑
超图倾斜数据合并根节点后转3dtiles
Force deduction solution summary 824 goat Latin
Getting started with RPC
Graphic data analysis | data cleaning and pretreatment
Add sequence number column to MySQL query result set
Swiftyjson analyse les fichiers json locaux
Force deduction solution summary 1037- effective boomerang
力扣编程题-解法汇总
没有文笔,大家多多包涵
力扣解法汇总473-火柴拼正方形
Force deduction solution summary - Sword finger offer II 114 Alien dictionary