Unique Path II

LeetCode #63

Description:

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.

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.

Idea:

除了遇到obstable需要考虑下，别的都和unique path一样。

Code:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> DP(m, vector<int>(n, 0));

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(obstacleGrid[i][j] == 1) { // Meet obstacle
                    if(i==0 && j==0) return 0;
                    else
                        DP[i][j]=0;
                }
                else{
                    if(i==0 && j==0) DP[i][j] = 1;
                    else if(i==0) DP[i][j] = DP[i][j-1];
                    else if(j==0) DP[i][j] = DP[i-1][j];
                    else DP[i][j] = DP[i-1][j] + DP[i][j-1];
                }
            }
        }

        return DP[m-1][n-1];

    }
};