即使走的再远,也勿忘启程时的初心
Hello,米娜桑们,这里是君兮_,如果给算法的难度和复杂度排一个排名,那么动态规划算法一定名列前茅。今天,我们通过由简单到困难的两道题目带大家学会动态规划中的路径问题
一 不同路径
1 题目解析
2 算法原理
状态表示
- 对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:
- i. 从dp[i, j] 位置出发,到某个位置去;
- ii. 从起始位置出发,到达dp [i, j] 位置。
分析一下题意,我们需要到达指定的位置,因此这⾥选择第⼆种定义状态表⽰的⽅式:
dp[i][j] 表⽰:⾛到dp[i, j] 位置处,此时一共有几条不同路径
状态转移方程
- 有了上面的状态表示,我们就需要将dp每个位置的值建立一定的联系,方便我们之后的分析
- 如果dp[i][j] 表⽰到达 [i, j] 位置的⽅法数,那么到达 [i, j] 位置之前的⼀⼩步,有两种情况:
- i. 从dp [i, j] 位置的上⽅( dp[i – 1, j] 的位置)向下⾛⼀步,转移到 dp[i, j] 位置;
- ii. 从 dp[i, j] 位置的左⽅( dp[i, j – 1] 的位置)向右⾛⼀步,转移到 dp[i, j] 位置。
由于我们要求的是有多少种⽅法,结合我们上面对题目的解析,因此我们的状态转移⽅程就可以写出了:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- 注意:这里还有一个很多初学者容易搞混的地方——很多人认为,你现在算出的是通往dp[i][j]这里不同种方法,那么dp[i][j]这一步不应该再加个1吗?
谨记我们这里算的是方法数,不是步数,因此当然不需要+1!
初始化
辅助节点初始化法
可以在dp表最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
-
i. 辅助结点⾥⾯的值要「保证后续填表是正确的」;
-
- 有关辅助节点,如果放在这一题来看的话,请问我们的dp[0][0]怎么算呢?
填表顺序:
返回值
3 编写代码
class Solution {
public:
int uniquePaths(int m, int n) {
//开辟m*n的dp表
vector<vector<int>>dp(m+1);
for(int i=0;i<dp.size();i++)
{
dp[i].resize(n+1,0);
}
dp[0][1]=1;//初始化
//状态转移方程
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
return dp[m][n];
}
};
二 下降路径最小和
1 题目解析
- 给你一个 n x n 的方形整数数组 matrix ,请你找出并返回通过 matrix 的下降路径的最小和 。
- 下降路径可以从第一行中的任何元素开始,并从每一行中选择一个元素在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col – 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
2 算法原理
状态表示
- 对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:
i. 从 [i, j] 位置出发,到达⽬标位置有多少种⽅式;
ii. 从起始位置出发,到达[i, j] 位置,⼀共有多少种⽅式
这⾥选择第⼆种定义状态表⽰的⽅式: - dp[i][j] 表示:到达[i, j] 位置时,所有下降路径中的最小和
- 路径问题的状态表示都是类似的,这里就不多阐释了,自己写的时候记得结合一下dp表中存的值符合题目要求就行
状态转移方程
- 先不考虑越界情况,对于普遍位置的dp[i, j] ,根据题意得,到达[i, j] 位置可能有三种情况:
i. 从正上⽅ [i – 1, j] 位置转移到 [i, j] 位置;
ii. 从左上⽅ [i – 1, j – 1] 位置转移到 [i, j] 位置;
iii. 从右上⽅ [i – 1, j + 1] 位置转移到 [i, j] 位置; - 我们要的是三种情况下的「最⼩值」,然后再加上数组中在 [i, j] 位置的值。
于是,我们可以得出状态转移方程
dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j +1])) + matrix[i][j]
初始化
- 从我在题意分析中画的那个图,可以明显看出每一行的最左位置和最右位置都存在越界,因此为了防止出现这种情况,我们还是采用上面讲的辅助节点的方法来进行初始化,不同的是,此时两边都存在可能越界,因此我们要初始化一行两列,示意图如下:
- 在这里对辅助节点进行初始化时,我们由于是求最小下降路径,为了不影响原dp表结果,此时先把辅助节点都填上一个较大的值。
- 此时,如果我们全都是较大的值,那么此时dp表第一行的初始化就会直接以这个较大值进行初始化,为了避免这种情况发生,我们将辅助节点的第一行全部初始化为0。
注意,重点来了: - 我们之前在辅助节点初始化方法中说过要注意下标的映射关系。
- 这里,我们需要把原数组的值填入到当前这个dp表中,但是现在的dp表多了一行两列,因此我们之前
dp[i][j]=min+matrix[i][j]
就需要改成dp[i][j]=min+matrix[i-1][j-1]
,这样才能满足对应的下标关系
填表顺序
- 题目已经明确告诉你了。从上到下
返回值
3 编写代码
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n=matrix.size();
//创建dp表
vector<vector<int>>dp(n+1,vector<int>(n+2));
//初始化
for(int i=1;i<=n;i++)
{
dp[i][0]=dp[i][n+1]=999999;
}
//填dp表
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
//状态转移方程
int ret=min(dp[i-1][j],min(dp[i-1][j+1],dp[i-1][j-1]));
//之前的值加上此时这里数组的值
dp[i][j]=ret+matrix[i-1][j-1];
}
}
//找最后一行的最小值
int min1=dp[n][1];
for(int i=2;i<=n;i++)
{
if(dp[n][i]<min1)
min1=dp[n][i];
}
return min1;
}
};
总结
- 好啦,我们今天的内容就先到这里啦!向这种题光看是看到只能看个一知半解的,如果你想学好的话一定要自己认真把上面两个路径规划的题写好,光看很多算法中的细节是无法体会到的。
- 有任何的问题和对文章内容的疑惑欢迎在评论区中提出,当然也可以私信我,我会在第一时间回复的!!
**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**
原文地址:https://blog.csdn.net/syf666250/article/details/134753525
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_27912.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。