63. 不同路径 II

古城微笑少年丶 2023-02-23 07:56 17阅读 0赞

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？  
![在这里插入图片描述][20200706011610785.png]  
网格中的障碍物和空位置分别用 1 和 0 来表示。  
说明：m 和 n 的值均不超过 100。  
示例 1:  
输入:  
\[ \[0,0,0\],  
\[0,1,0\],  
\[0,0,0\] \]  
输出: 2  
解释:  
3x3 网格的正中间有一个障碍物。  
从左上角到右下角一共有 2 条不同的路径：

1.  向右 -> 向右 -> 向下 -> 向下
2.  向下 -> 向下 -> 向右 -> 向右  
    来源：力扣（LeetCode）[题目链接][Link 1]

入门级动态规划：

class Solution {
        
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        
            int row = obstacleGrid.size();
            if(row == 0) return 0;
            int col = obstacleGrid[0].size();
            if(obstacleGrid[0][0] == 1) return 0;
            obstacleGrid[0][0] = 1;//初始化边界
            for(int i = 1; i < row; i++) {
        
                if(obstacleGrid[i][0] == 1) obstacleGrid[i][0] = 0;
                else obstacleGrid[i][0] = obstacleGrid[i-1][0];
            }
            for(int j = 1; j < col; j++) {
        
                if(obstacleGrid[0][j] == 1) obstacleGrid[0][j] = 0;
                else obstacleGrid[0][j] = obstacleGrid[0][j-1];
            }
            //递推
            for(int i = 1; i < row; i++){
        
                for(int j = 1; j < col; j++){
        
                    if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0;
                    else obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
                }
            }
            return obstacleGrid[row-1][col-1];
        }
    };

一维滚动数组优化：（官方答案）

class Solution {
        
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        
            int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
            vector <int> f(m);
    
            f[0] = (obstacleGrid[0][0] == 0);
            for (int i = 0; i < n; ++i) {
        
                for (int j = 0; j < m; ++j) {
        
                    if (obstacleGrid[i][j] == 1) {
        
                        f[j] = 0;
                        continue;
                    }
                    if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
        
                        f[j] += f[j - 1];
                    }
                }
            }
    
            return f.back();
        }
    };

[20200706011610785.png]: https://img-blog.csdnimg.cn/20200706011610785.png
[Link 1]: https://leetcode-cn.com/problems/unique-paths-ii