当前位置:网站首页>Unique paths II of leetcode topic analysis
Unique paths II of leetcode topic analysis
2022-06-23 08:39: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.
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];
}边栏推荐
- 2- use line segments to form graphics and coordinate conversion
- Vulnhub | dc: 3 | [actual combat]
- When easynvr service is started, video cannot be played due to anti-virus software interception. How to deal with it?
- Optimize your gradle module with a clean architecture
- Spirit matrix for leetcode topic analysis
- Talk about the implementation principle of @autowired
- [operating steps] how to set the easynvr hardware device to be powered on without automatic startup?
- Point cloud library PCL from introduction to mastery Chapter 10
- Assembly (receive several n-digit decimal values (0~65535) from the keyboard and display their sum in different base numbers.)
- 谈谈 @Autowired 的实现原理
猜你喜欢
随机推荐
Map (set) operation in go language
为什么用生长型神经气体网络(GNG)?
Structure and usage of transform
6-shining laser application of calayer
给你的win10装一个wget
[cloud computing] GFS ideological advantages and architecture
Go 数据类型篇(二)之Go 支持的数据类型概述及布尔类型
Pyspark on HPC (Continued): reasonable partition processing and consolidated output of a single file
Deep learning ----- different methods to implement lenet-5 model
[paper notes] catching both gray and black swans: open set supervised analog detection*
Chapter 1 open LDAP master-slave synchronization tower construction
Vulnhub | dc: 3 | [actual combat]
Why do we say that the data service API is the standard configuration of the data midrange?
Single core driver module
Set interface and set sub implementation classes
usb peripheral 驱动 - configfs
How to sort a dictionary by value or key?
Implementing an open source app store with swiftui
Leetcode topic analysis set matrix zeroes
Image segmentation - improved network structure








