Short Recursive Java DP Solution 1ms O(XY)


  • 0
    F
    public class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int[][] memo = new int[obstacleGrid.length][obstacleGrid[0].length];
            return pathHelper(obstacleGrid,0,0,memo);
        }
        public int pathHelper(int[][] grid, int row, int col, int[][] memo){
            //Base Case #1: If out of bounds or a 1 encountered or saved result was -1(meaning no path exists from it) return 0
            if(row > grid.length-1 || col > grid[0].length - 1 || grid[row][col] == 1 || memo[row][col] == -1) return 0;
            //Base Case #2: Valid goal is reached if point is a 0 and row and col are at bottom right of grid
            if(grid[row][col] == 0 && row == grid.length-1 && col == grid[0].length - 1) return 1;
            //Checking if we haven't already processed row and col
            if(memo[row][col] == 0){
                memo[row][col] = pathHelper(grid,row+1,col,memo) + pathHelper(grid,row,col+1,memo);
                //If memo[row[col] is 0 then there is no paths from this point so we can ignore it later on for efficency
                if(memo[row][col] == 0) memo[row][col] = -1;
            }
            //Returning saved results. Note memo[row][col] still has a chance to be -1 from the prior if statement.
            return memo[row][col] == -1 ? 0 : memo[row][col];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.