【动态规划】06路径问题_不同路径II_C++(medium)

2023-12-14 05:12:06

题目链接:leetcode不同路径II


目录

题目解析:

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码


题目解析:

题目让我们求在考虑网格中有障碍物的情况下,从左上角到右下角将会有多少条不同的路径

由题可得:

机器人位于一个?m x n?网格的左上角?

机器人每次只能向下或者向右移动一步

我们拿示例1来分析:

则根据题目要求我们只能向下或者向右移动一步,不能向上或向左回退,而且要避开障碍物;

所以这里我们一共有2种走法:


算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义(是什么?)

dp[i][j]表示到达i*j时一共有多少种方式;

这种状态表示怎么来的?

1.题目要求

经验:以i*j位置为结尾,

题目让我们求到达右下角有多少种方式(需要避开障碍物),那么这里我们可以dp[i][j]来表示。

所以这里我们用i*j表示右下角位置;

2.经验+题目要求

用之前或者之后的状态,推导出dp[i][j]的值;

根据最近的最近的一步,来划分问题

我们先不考虑有障碍物的情况:

当机器人到达dp[i-1][j]时,我们知道它到达[i-1][j]有dp[i-1][j]方式,

此时只需要从[i-1][j]往下走一步就可以到达目标位置,即:

……-->[i-1][j]-->(往下走一步)[i][j];

……-->[i-1][j]-->(往下走一步)[i][j];

……-->[i-1][j]-->(往下走一步)[i][j];

……

所以往下走一步就可以到达目标位置的方式就有dp[i-1][j]种;

那么同理,

当机器人到达dp[i][j-1]时,我们知道它到达[i][j-1]有dp[i][j-1]方式,

此时只需要在到达[i][j-1]方式的后面往右边走一步就可以到达目标位置,即:

……-->[i][j-1]-->(往右边走一步)[i][j];

……-->[i][j-1]-->(往右边走一步)[i][j];

……-->[i][j-1]-->(往右边走一步)[i][j];

……

所以往右边走一步就可以到达目标位置的方式就有dp[i-1][j]种;

综上所述,我们只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到,到达[i][j]位置的总方法,

即:

dp[i][j]=dp[i-1][j]+dp[i][j-1];

好,分析完了没有障碍物的情况,现在我们再来加上障碍物:

从上面的分析我们知道到达i*j位置,只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到

如果[i][j-1]与[i-1][j]之中有一个是障碍物时:

那么有效的路线就只有上面那条,那么只要把有障碍物的地方设为0,就不会影响状态转移方程了。

2.状态转移方程

dp[i]等于什么?

由我们的状态转移方程得:

在0行0列的时候越界,所以我们这里可以在m*n的外围多加1行1列,如图:

还有一个问题是:

我们要拿新增用来初始化的行和列要初始化为几呢?

假设:如果所需要到达的位置就在机器人所在的位置,此时有一种方式

根据状态转移方程,在[0][1]与[1][0]位置要有一个位置需要初始化为1,其他位置初始化为0

我们这里选择[0][1]初始化为1

3.初始化

(保证填表的时候不越界)

4.填表顺序

(为了填写当前状态的时候,所需要的状态已经计算过了)

这里所需要的状态是:到达该位置的上面和左边位置的方式

所以填表顺序:

从上到下填写每一行

从左到右填写每一列

5.返回值

(根据题目要求和状态表示)

综上分析:

返回值为:dp[m][n];


编写代码:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    //1.创建dp表
    //2.初始化
    //3.填表
    //4.返回结果
    int m=obstacleGrid.size();
    int n=obstacleGrid[0].size();
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    dp[0][1]=1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(obstacleGrid[i-1][j-1]==1)
            {
                dp[i][j]=0;
            }
            else
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    return dp[m][n];
    }
};

文章来源:https://blog.csdn.net/lsj1345714539566/article/details/134912523
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。