1ms Java DP solution, 2 methods.


  • 0
    M

    method 1: time O(n^2), space O(n^2).
    Very easy to understand. Count path from the left bottom grid. Use a matrix to record the result. The element in the matrix means the number of paths starting from here.

        public int uniquePathsWithObstacles_Matrix(int[][] obstacleGrid) {
            if(obstacleGrid == null || obstacleGrid[0][0]==1) return 0;
            final int n = obstacleGrid.length, m = obstacleGrid[0].length;
            int[][] dp = new int[n][m];
            int init = 1;
            for(int i=n-1; i>=0; i--){
                if(obstacleGrid[i][m-1]==1)
                    init = 0;
                dp[i][m-1] = init;
            }
            init = 1;
            for(int j=m-1; j>=0; j--){
                if(obstacleGrid[n-1][j]==1)
                    init = 0;
                dp[n-1][j] = init;
            }
            
            for(int i=n-2; i>=0; i--){
                for(int j=m-2; j>=0; j--){
                    if(obstacleGrid[i][j]==0)
                        dp[i][j] = dp[i+1][j] + dp[i][j+1];
                }
            }
            return dp[0][0];
        }
    

    method 2: time O(n^2), space O(n).
    Simplified from method 1. Just use array to record the result. In last method we only need the left element and the down element. Actually, the method can be O(1) in space complexity.

        public int uniquePathsWithObstacles_Array(int[][] obstacleGrid) {
        	if(obstacleGrid  == null) return 0;
        	final int N = obstacleGrid.length, M = obstacleGrid[0].length; 
        	int[] dp = new int[M+1];
        	int init = 1;
        	for(int j=M-1; j>=0; j--){
        		if(obstacleGrid[N-1][j] == 1)
        			init = 0;
        		dp[j] = init;
        	}
        	for(int i=N-2; i>=0; i--){
        		for(int j=M-1; j>=0; j--){
        			if(obstacleGrid[i][j]==1){
        				dp[j] = 0;
        			} else {
        				dp[j] = dp[j] + dp[j+1];
        			}
        		}
        	}
        	return dp[0]; 
    	}
    

Log in to reply
 

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