10 lines Java, O(m) space DP, explained


  • 0
    C
       public int uniquePathsWithObstacles(int[][] grid) {
            int n = grid.length, m = grid[0].length;
            int [] dp = new int[m+1];
            dp[m-1]=1;
            for(int i=n-1;i>=0;i--){
                for(int j=m-1;j>=0;j--){
                    if(grid[i][j]==1) dp[j]=0;
                    else dp[j]=dp[j+1]+dp[j];
                }
            }
            return dp[0];
        } 
    

    The idea is same to other bottom up dp solutions.

    • dp[i][j](total paths) = dp[i+1][j](paths via down neighbor) + dp[i][j+1](paths via right neighbor)
    • Compared to UniquePaths, the only adaption need to make is make dp[i][j]=0 if it's an obstacle.

    Observations:

    • only need to save the result of previous row, instead of entire matrix
    • initialize dp array with one more element will eliminate the necessity to check if i+1,j+1 is in boundary.

Log in to reply
 

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