题目链接: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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution
{
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid)
{
if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0)
return 0;
vector<vector<int> > vvi(obstacleGrid.size() + 1, vector<int>(obstacleGrid[0].size() + 1, 0));
vvi[0][1] = 1;
for(int i = 1; i < vvi.size(); ++ i)
for(int j = 1; j < vvi[i].size(); ++ j)
vvi[i][j] = obstacleGrid[i - 1][j - 1] == 0 ? vvi[i][j - 1] + vvi[i - 1][j] : 0;
return vvi[vvi.size() - 1][vvi[0].size() - 1];
}
};