Q-10 Unique Paths II - LeetCode
Sat Sep 09 2023 15:03:31 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length , n = grid[0].length;
//if first cell is 1 only , first cell is not checked in recursion
if(grid[m-1][n-1] == 1)
return 0;
// return solve(grid , m-1 , n-1 , new Integer[m][n]);
//tabulization -> 2*m*n | Sc - m*n (dp array)
int[][] dp = new int[m][n];
// dp[0][0] = 1;
for(int i = 0 ;i < m ; i++){
for(int j =0 ; j < n ; j++){
//base case
if(i == 0 && j == 0)
dp[i][j] = 1;
else{
int down = 0 , right = 0;
if(i-1 >= 0 && grid[i-1][j] != 1)
down = dp[i-1][j];
if(j-1>=0 && grid[i][j-1] != 1)
right = dp[i][j-1];
dp[i][j] = (down + right);
}
}
}
return dp[m-1][n-1];
}
//recursion 2^(m*n) + memoization 2*m*n| Sc- m*n(recursion stack height) + m*n(dp array)
public int solve(int[][] grid , int r , int c , Integer[][] dp ){
if(r == 0 && c == 0 )
return 1;
if(dp[r][c] != null)
return dp[r][c];
int down = 0 , right = 0;
if(r-1 >= 0 && grid[r-1][c] != 1)
down = solve(grid , r-1,c ,dp);
if(c-1>=0 && grid[r][c-1] != 1)
right = solve(grid , r , c-1 , dp);
return dp[r][c] = (down + right);
}
}
content_copyCOPY
https://leetcode.com/problems/unique-paths-ii/
Comments