Repository navigation
Expand file tree
/
Copy pathUniquePathsii.java
More file actions
105 lines (66 loc) · 2.58 KB
/
Copy pathUniquePathsii.java
File metadata and controls
105 lines (66 loc) · 2.58 KB
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// Unique Paths II
// You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
// An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
// Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
// The testcases are generated so that the answer will be less than or equal to 2 * 109.
class UniquePathsii{
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n= obstacleGrid[0].length;
int dp[][] = new int[m][n];
// for(int i = 0 ; i<m ;i++){
// Arrays.fill(dp[i],-1);
// }
// return mazememo(m-1,n-1,obstacleGrid, dp );
return tabulation(obstacleGrid);
}
public int mazememo(int i, int j, int [][] obstacleGRid , int dp[][]){
if(i<0 || j<0){
return 0;
}
if((i>=0 && j>=0 ) && obstacleGRid[i][j] ==1){
return 0;
}
if(i==0 && j==0){
return 1;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
int up = mazememo(i-1,j,obstacleGRid,dp );
int left = mazememo(i,j-1, obstacleGRid, dp);
dp[i][j] = up+left;
return dp[i][j];
}
public int tabulation( int[][] obstacleGrid){
int m = obstacleGrid.length;
int n= obstacleGrid[0].length;
int dp[][] = new int[m][n];
for(int i =0; i<m; i++){
for(int j =0 ; j<n ; j++){
if((i==0 && j==0) && obstacleGrid[i][j] != 1 ) dp[i][j] = 1;
else{
int left =0;
int up =0;
if(obstacleGrid[i][j]==1){
dp[i][j] = 0;
continue;
}
if(i>0) up = dp[i-1][j];
if(j>0) left = dp[i][j-1];
dp[i][j] = up + left;
}
}
}
return dp[m-1][n-1];
}
public static void main(String[] args) {
UniquePathsii uniquePathsii = new UniquePathsii();
int[][] obstacleGrid = {
{0,0,0},
{0,1,0},
{0,0,0}
};
System.out.println(uniquePathsii.uniquePathsWithObstacles(obstacleGrid));
}
}