首页 > 代码库 > [C++]LeetCode: 78 Unique Paths II

[C++]LeetCode: 78 Unique Paths II

2024-10-28 14:40:02   212人阅读

题目：

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.

思路：这道题和LeetCode: 56 Unique Paths非常相似，只是这次首先要先判断是否有障碍。不是每次都有两个选择（向右，向下）。因为有了这个，我们不能直接求和得到结果。递推式和unique path一样，不过我们每次都要先判断是否有障碍，如果有，dp[i][j] = 0,如果没有dp[i][j] = dp[i-1][j] + dp[i][j-1]. 所以，实际上我们还是只需要一个一维数组，因为更新时的信息足够了。

Attention：
1. 注意和unique path的区别，首先是一维数组的初始化，由于我们还需要判断第一行是否存在障碍，所以初始化时为0.

<span style="font-size:14px;">vector<int> dp(col, 0);</span>
2. 由于我们还需要计算第一行的dp值，所以循环范围从0~row, 0~col.注意计算递归式时，dp[ci] = dp[ci] + dp[ci-1],要先判断ci>0.

<span style="font-size:14px;">for(int ri = 0; ri < row; ri++)
        {
            for(int ci = 0; ci < col; ci++)
            {</span>
3. 我们需要初始化dp[0], 如果obstacleGrid[0][0] = 1, 则会重置dp[0] 为0， 否则dp[0]= 1,将用于更新下一个动态规划表的值。

<span style="font-size:14px;">if(obstacleGrid[ri][ci] == 1)
{
   dp[ci] = 0;
}
else
{
   if(ci > 0)
   dp[ci] = dp[ci] + dp[ci-1];
}</span>
复杂度：时间复杂度，一次遍历O(n), 空间复杂度，一维数组，O(N)

AC Code:

<span style="font-size:14px;">class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        if(row == 0 || col == 0) return 0;
        
        vector<int> dp(col, 0);
        dp[0] = 1;
        
        for(int ri = 0; ri < row; ri++)
        {
            for(int ci = 0; ci < col; ci++)
            {
                if(obstacleGrid[ri][ci] == 1)
                {
                    dp[ci] = 0;
                }
                else
                {
                    if(ci > 0)
                        dp[ci] = dp[ci] + dp[ci-1];
                }
            }
        }
        
        return dp.back();
    }
};</span>





[C++]LeetCode: 78 Unique Paths II


联系
我们