1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0){
return 0;
}
int row = obstacleGrid.length;
int column = obstacleGrid[0].length;
int lookup[] = new int[column];
lookup[column-1] = obstacleGrid[row-1][column-1]==1?0:1;
for (int i = column-2; i >= 0; i--){
lookup[i] = obstacleGrid[row-1][i] == 1?0:lookup[i+1];
}
for (int i = row-2; i >= 0; i--){
lookup[column-1] = obstacleGrid[i][column-1] == 1?0:lookup[column-1];
for (int j = column-2; j >= 0; j--){
lookup[j] = obstacleGrid[i][j] == 1?0:(lookup[j]+lookup[j+1]);
}
}
return lookup[0];
}
}
|
No comments:
Post a Comment