Unique Paths II (Medium)

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.

Analysis

在I版本上稍微改一下就好了。

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//C++
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size();
        if(m==0)    return 0;
        int n = obstacleGrid[0].size();
        if(n==0)    return 0;
        vector<vector<int> >dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]==1)
                break;
            dp[i][0]=1;
        }
        for(int i = 0; i<n;i++){
            if(obstacleGrid[0][i]==1)
                break;
            dp[0][i]=1;
        }
        for(int i = 1;i<m;i++)
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==1)
                    continue;
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        return dp[m-1][n-1];
    }
};