200ms Java code (DP)


  • 0
    Z
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int p=obstacleGrid.length,q=obstacleGrid[0].length;
        int[][] map=new int[p][q];
        for(int i=0;i<p;i++)
            for(int j=0;j<q;j++)
                map[i][j]=-1;
        int res=recurUniquePaths(map,p-1,q-1,p-1,q-1,obstacleGrid);
        return res==-1?0:res;
        
    }
    private int recurUniquePaths(int[][] map, int m, int n, int p, int q,int[][]obs){
        if(map[m][n]==-1){
            if(obs[p-m][q-n]==1){
                map[m][n]=0;
                return 0;
            }
            if(m==0 && n==0) map[0][0]=1;
            else if(n==0) map[m][n]=recurUniquePaths(map,m-1,n,p,q,obs);
            else if(m==0) map[m][n]=recurUniquePaths(map,m,n-1,p,q,obs);
            else map[m][n]=recurUniquePaths(map,m,n-1,p,q,obs)+recurUniquePaths(map,m-1,n,p,q,obs);
        }
        return map[m][n];
    }

Log in to reply
 

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