115.Unique Paths II

1.Description(Easy)

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 as1and0respectively in the grid.

Notice

m and n will be at most 100.

Example

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 is2.

2.Code

初始化第0行0列都只有一种走法

初始化的时候注意，若此处是1，则0行/0列后面所有的

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid==null || obstacleGrid[0].length==0){
            return 0;
        }
        if(obstacleGrid[0]==null || obstacleGrid[0].length==0){
            return 0;
        }

        int n=obstacleGrid.length;
        int m=obstacleGrid[0].length;

        //state:
        int[][] f=new int[n][m];

        //Initialization:
        /*if(obstacleGrid[0][0]!=1){
            f[0][0]=1;
        }
        else{
            return -1;
        }*/

        for(int i=0;i<m;i++){
            if(obstacleGrid[0][i]!=1){
                f[0][i]=1;
            }
            else{
                break;
            }
        }
        for(int i=0;i<n;i++){
            if(obstacleGrid[i][0]!=1){
                f[i][0]=1;
            }
            else{
                break;
                }
        }


        //function:
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(obstacleGrid[i][j]!=1){
                    f[i][j]=f[i-1][j]+f[i][j-1];
                }
                else{
                    f[i][j]=0;
                }
            }
        }

        //answer:
        return f[n-1][m-1];
    }