算法日常・每日刷题--＜动态规划＞6

63. 不同路径 II - 力扣（LeetCode）

题目

一个机器人位于网格左上角，网格里存在障碍物，obstacleGrid[i][j]==1代表该位置有障碍物，不能通行。机器人只能向下、向右走，求从左上角走到右下角一共有多少路径。障碍物位置无法经过。

思路解析

状态转移和无障碍物版本几乎一样：

\(dp[i][j] = dp[i-1][j]+dp[i][j-1]\)

增加一条规则：

如果当前网格位置存在障碍物，dp[i][j]=0，代表到达该点路径数为 0，后面的格子也不会从这里继承路径。

初始化技巧沿用：dp[0][1]=1，简化第一行第一列边界处理。

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

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2503_92261635/article/details/167040842