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); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter