63. Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

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
Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

类似于上一道题，只不过添加了障碍物，那么这种情况下需要考虑的是：
如果某一点的OG为1，那么这一点便没有路径可走，因此直接赋值为dp[i][j]=0即可，此时若考虑其右边的点，则只有上边的路径可走，其左边的路径值为0.
同时记得考虑m=0时和n=0时，只接受上边或左边传入。
另外考虑初始情况OG[0][0]是否为1，是的话直接return 0，不是赋值dp[0][0]为1.

Solution

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