LeetCode 63. Unique Paths II

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 63. Unique Paths II 原题链接中等

作者：

cornerCao , 2018-03-27 21:54:39 , 所有人可见 , 阅读 2829

6

1

题目描述

是62题Unique Paths的进阶版，考虑在网格中加入了障碍，在网格图中，0该网格是空的，1表示该网格有障碍，例如

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

这样一个网格，不能经过中间的格子，从左上角到右下角的路线数目为2.

样例

输入：网格的0 1矩阵
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出：2
解释：不能经过中间的格子，从左上角到右下角的路线数目为2

算法

(动态规划) $O(mn)$

类似于62题Unique Paths，每一个网格都可以由该网格左边或上边的网格转移过来，因此到达某一点的路径数等于到达它上一点的路径数与它左边的路径数之和，不同的是，当某个网格有障碍时，到达该网格的路径数维0。这还是一个递推问题，考虑用动态规划。动态规划数组dp[i][j] = 起点到点(i, j)的路径总数。于是我们就得到递推关系式：当网格为0时，dp[i][j] = dp[i][j-1] + dp[i-1][j]；当网格为1（说明该网格是障碍物），dp[i][j]=0。

C++ 代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        if(m == 0)return 0;
        int n = obstacleGrid[0].size();
        if(n == 0)return 0;
        int dp[101][101];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1 - obstacleGrid[0][0];
        for(int i = 0; i < m; i++){
            for(int j = 0; j< n; j++){
                if(obstacleGrid[i][j] == 1)
                    dp[i][j] = 0;
                else{
                    if(i > 0)
                        dp[i][j] += dp[i-1][j];
                    if(j > 0)
                        dp[i][j] += dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

12 评论

这是空格 2023-03-27 20:26

简单版，初始化分开，第一行和第一列

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        if(obstacleGrid[0][0] || obstacleGrid[m-1][n-1])return 0;
        vector<vector<int>> dp(m,vector<int>(n));
        dp[0][0]=1;
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]==1)break;
            dp[i][0]=1;
        }

        for(int i=0;i<n;i++){
            if(obstacleGrid[0][i]==1)break;
            dp[0][i]=1;//cout<<"here"<<endl;
        }
        //dp[i][j]=dp[i-1][j]+dp[i][j-1]
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==0){
                    int t1=0,t2=0;
                    if(!obstacleGrid[i-1][j])t1=dp[i-1][j];
                    if(!obstacleGrid[i][j-1])t2=dp[i][j-1];
                    dp[i][j]=t1+t2;
                }
            }
        }
        return dp[m-1][n-1];
    }
};

Omega_ 2020-04-03 15:56

感觉有点懵了 dfs和dp有点不知道啥时候该用什么了

小呆呆 2019-09-03 22:50

dp[0][0]可以一开始就设置为1，如果该位置是障碍物的话，后面的会自动赋值为0

一只菜鸡 2019-09-02 09:09

谢谢楼主的题解，　同被卡int, hint 里面说 m and n will be at most 100，　怎么从这个估算出会超过int的呢？

cornerCao 2019-09-02 14:23

假如整个图没有障碍物的话，所有可能的线路数是$C^{100}_{200}$，还是可能超过int型的

一只菜鸡 2019-09-02 23:24 回复了 cornerCao 的评论

明白了，多谢！

wt 2019-08-29 10:09

请问dp[0][0] = 1 - obstacleGrid[0][0];怎么理解呢
以及第二个for循环里面的else为什么判断i 和 J 大于零呢
望大佬赐教

cornerCao 2019-09-02 14:20

如果 obstacleGrid[0][0]=0的话说明(0, 0)点没有障碍，到(0, 0)的线路数为1，如果 obstacleGrid[0][0]=1的话说明(0, 0)点有障碍，所以没办法到(0, 0)点，线路数为0；
i和j大于0的话i-1和j-1都不会越界，如果等于0的话，就不能从(i-1, j)或者(i, j-1)更新过来了