63. 不同路径 II - 力扣(LeetCode)编辑https://leetcode.cn/problems/unique-paths-ii/description/https://leetcode.cn/problems/unique-paths-ii/description/问题描述:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。文章来源:https://www.toymoban.com/news/detail-793138.html
分析:文章来源地址https://www.toymoban.com/news/detail-793138.html
- dp[i][j]表示到达第 i 行第 j 列有多少种路径。(i,j 从 0 开始)
- 如果起点或终点处有障碍,直接return 0 ;
- 初始化dp数组,dp[0][0]=1,障碍处dp[i][j]=0;
- 依次初始化第一列和第一行,非障碍处dp等于上一行(列)的dp
- 遍历剩余部分,非障碍处dp等于左+上的dp dp[i][j]=dp[i-1][j]+dp[i][j-1]
- 返回终点处dp[m-1][n-1]
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if(obstacleGrid[0][0]==1) return 0;
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0)); //创建m行n列数组;
dp[0][0]=1;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(obstacleGrid[i][j]==1) dp[i][j]=0;
}
}
for(int i=1;i<m;i++){ //第一列
if(obstacleGrid[i][0]!=1) dp[i][0]=dp[i-1][0];
}
for(int j=1;j<n;j++){ //第一行
if(obstacleGrid[0][j]!=1) dp[0][j]=dp[0][j-1];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(obstacleGrid[i][j]!=1) dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
到了这里,关于动态规划——不同路径II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!