题目链接: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];
    }
};