题目链接：Unique Paths II
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.
这道题的要求是在Unique Paths的网格中添加障碍物，计算用多少路径。障碍物用1表示，空地用0表示。
这是Unique Paths的后继版本，不过采用动态规划是最直接的，递推公式同样是dp[i][j] = dp[i][j-1] + dp[i-1][j]，只不过这是在[i, j]位置是空地的时候，而当[i, j]位置是障碍物的时候，dp[i][j] = 0。
时间复杂度：O(mn)
空间复杂度：O(mn)
1 class Solution
2 {
3 public:
4 int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid)
5 {
6 if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0)
7 return 0;
8
9 vector<vector<int> > vvi(obstacleGrid.size() + 1, vector<int>(obstacleGrid[0].size() + 1, 0));
10 vvi[0][1] = 1;
11 for(int i = 1; i < vvi.size(); ++ i)
12 for(int j = 1; j < vvi[i].size(); ++ j)
13 vvi[i][j] = obstacleGrid[i - 1][j - 1] == 0 ? vvi[i][j - 1] + vvi[i - 1][j] : 0;
14
15 return vvi[vvi.size() - 1][vvi[0].size() - 1];
16 }
17 };