My 1 ms Java solution


  • 0

    The basic idea is f(m, n) = f(m-1, n)+f(m, n-1), and f(m, n) should be 0, if obstacleGrid[m][n] is 1.

    public class Solution {
            public int uniquePathsWithObstacles(int[][] obstacleGrid) {
                int m=obstacleGrid.length;
                int n=obstacleGrid[0].length;
                int [][] r=new int [m][n];
            
            for(int i=0;i<m;i++){
                if(obstacleGrid[i][0]==0){
                    if(i>=1&&r[i-1][0]!=0){ // When there is an obstacle before r[i][0], r[i][0] should be 0.
                        r[i][0]=1;
                    }else if(i==0){
                        r[i][0]=1;
                    }
                    
                }
            }
            
            for(int i=0;i<n;i++){
                if(obstacleGrid[0][i]==0){
                    if(i>=1&&r[0][i-1]!=0){
                        r[0][i]=1;
                    }else if(i==0){
                        r[0][i]=1;
                    }
                }
            }
            
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++){
                    if(obstacleGrid[i][j]!=0){
                        r[i][j]=0;
                    }else{
                        r[i][j]=r[i-1][j]+r[i][j-1];
                    }
                }
            }
            
            return r[m-1][n-1];
        }
    }

Log in to reply
 

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