Java dp solutions (O(n*n), O(n) space).


  • 1
    C
    // O(n*n) space
    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        int row = obstacleGrid.length, col = obstacleGrid[0].length;
        int dp[][] = new int[row][col];
        dp[0][0] = 1-obstacleGrid[0][0];
        for (int i=1; i<row; i++)
            dp[i][0] = dp[i-1][0]*(1-obstacleGrid[i][0]);
        for (int j=1; j<col; j++)
            dp[0][j] = dp[0][j-1]*(1-obstacleGrid[0][j]);
        for (int i=1; i<row; i++) 
            for (int j=1; j<col; j++)
                dp[i][j] = (dp[i-1][j]+dp[i][j-1])*(1-obstacleGrid[i][j]);
        return dp[row-1][col-1];
    }
    
    // O(n) space
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length, col = obstacleGrid[0].length;
        int dp[] = new int[col];
        dp[0] = 1-obstacleGrid[0][0];
        for (int j=1; j<col; j++)
            dp[j] = dp[j-1]*(1-obstacleGrid[0][j]);
        for (int i=1; i<row; i++) {
            dp[0] *= 1-obstacleGrid[i][0];
            for (int j=1; j<col; j++) 
                dp[j] = (dp[j-1]+dp[j])*(1-obstacleGrid[i][j]);
        }
        return dp[col-1];
    }

Log in to reply
 

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