Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.

Solution1：DP

思路：
Time Complexity: O(mn) Space Complexity: O(mn)

Solution2：DP with space optimization

思路：
Time Complexity: O(mn) Space Complexity: O(2n)

Solution3：DP with space optimization

思路：
Time Complexity: O(mn) Space Complexity: O(n)

也可以利用输入直接inplace

Solution1 Code：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[][] dp = new int[m + 1][n + 1]; // add dummy init row and col
        dp[0][1] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(obstacleGrid[i - 1][j - 1] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

Solution2 Code：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[] pre = new int[n + 1];
        int[] cur = new int[n + 1];
        
        pre[1] = 1;
        
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(obstacleGrid[i - 1][j - 1] == 0) {
                    cur[j] = cur[j - 1] + pre[j];
                }
                else {
                    cur[j] = 0;
                }
            }
            int[] tmp = pre;
            pre = cur;
            cur = tmp;
        }
        
     
        return pre[n];
    }
}

Solution3 Code：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[j] += dp[j - 1];
                }
                else if (j > 0) {
                    p[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}