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

  • 0
       public int uniquePathsWithObstacles(int[][] grid) {
            int n = grid.length, m = grid[0].length;
            int [] dp = new int[m+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.


    • 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.