网站开发顶岗报告,建网站的大公司,做旅游网站的,域名升级系统自动更新君兮_的个人主页 即使走的再远#xff0c;也勿忘启程时的初心 C/C 游戏开发 Hello,米娜桑们#xff0c;这里是君兮_#xff0c;如果给算法的难度和复杂度排一个排名#xff0c;那么动态规划算法一定名列前茅。今天#xff0c;我们通过由简单到困难的两道题目带大家学会动… 君兮_的个人主页 即使走的再远也勿忘启程时的初心 C/C 游戏开发 Hello,米娜桑们这里是君兮_如果给算法的难度和复杂度排一个排名那么动态规划算法一定名列前茅。今天我们通过由简单到困难的两道题目带大家学会动态规划中的路径问题 好了废话不多说开始我们今天的学习吧 动态规划之路径问题 一 不同路径1 题目解析2 算法原理状态表示状态转移方程初始化辅助节点初始化法 填表顺序返回值 3 编写代码 二 下降路径最小和1 题目解析2 算法原理状态表示状态转移方程初始化填表顺序返回值 3 编写代码 总结 一 不同路径
原题目leetcode链接在这哦 不同路径
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
初始化
初始化的主要目的有两个 1.防止发生越界访问 2.方便我们从已知的信息推出我们需要的信息 这里教给大家一个做动态规划会经常使用的初始化方法 辅助节点初始化法
可以在dp表最前⾯加上⼀个「辅助结点」帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要「保证后续填表是正确的」 ii. 「下标的映射关系」。 好了相信到这里大家还是一头雾水下面我来展开讲讲 有关辅助节点如果放在这一题来看的话请问我们的dp[0][0]怎么算呢 因此在本题中我们需要「添加⼀⾏」并且「添加⼀列」来避免上述越界情况的发生 因此就有了第一点我们的辅助节点中保存的值必须保证对我们的题目的解答没有影响比如在这个题需将 dp[0][1] 或者dp[1][0]的位置初始化为1 剩下创建的值初始化为0这样就能保证dp[1][1]位置的初始化 那么为什么从dp[1][1] 开始呢我们的辅助队列相当于在最上后最右的位置帮我们又创建了一行一列来初始化此时机器人所处的位置就变为了dp[1][1]了 有关第二点我们加了一行一列下标的初始位就不再是dp[0][0]了因此我们最后返回的值也不是dp[m-1][n-1]而是dp[m][n].。在这个题中下标的映射没啥太大的影响具体的细节我们放在下个题再讨论
填表顺序
根据状态转移⽅程和题目分析的推导来看填表的顺序就是「从上往下」填每⼀⾏在填写每⼀⾏的时候「从左往右」填每一列
返回值
上面在辅助节点已经说过了返回值为dp[m][n] 完成上面的算法原理分析下面我们来具体写一下代码 3 编写代码
class Solution {
public:int uniquePaths(int m, int n) {//开辟m*n的dp表vectorvectorintdp(m1);for(int i0;idp.size();i){dp[i].resize(n1,0);}dp[0][1]1;//初始化//状态转移方程for(int i1;im;i){for(int j1;jn;j)dp[i][j]dp[i-1][j]dp[i][j-1];}return dp[m][n];}
};照这上面讲的算法原理一步一步照搬挺容易ac的这里就不细讲了重点还是放在下面这个题上 二 下降路径最小和
原题leetcode链接在这里 下降路径最小和
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]minmatrix[i][j]就需要改成dp[i][j]minmatrix[i-1][j-1] 这样才能满足对应的下标关系
填表顺序
题目已经明确告诉你了。从上到下
返回值
注意这⾥不是返回 dp[m][n] 的值题⽬要求「只要到达最后⼀⾏」就⾏了因此这⾥应该返回「dp表中最后⼀⾏的最⼩值」 3 编写代码
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {int nmatrix.size();//创建dp表vectorvectorintdp(n1,vectorint(n2));//初始化for(int i1;in;i){dp[i][0]dp[i][n1]999999;}//填dp表for(int i1;in;i){for(int j1;jn;j){//状态转移方程int retmin(dp[i-1][j],min(dp[i-1][j1],dp[i-1][j-1]));//之前的值加上此时这里数组的值dp[i][j]retmatrix[i-1][j-1];}}//找最后一行的最小值int min1dp[n][1];for(int i2;in;i){if(dp[n][i]min1)min1dp[n][i];}return min1;}
};照着上面的算法原理步骤走ac不是so easy啦 总结
好啦我们今天的内容就先到这里啦向这种题光看是看到只能看个一知半解的如果你想学好的话一定要自己认真把上面两个路径规划的题写好光看很多算法中的细节是无法体会到的。有任何的问题和对文章内容的疑惑欢迎在评论区中提出当然也可以私信我我会在第一时间回复的 新人博主创作不易如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力 **可莉请求你们三连支持一下博主点击下方评论点赞收藏帮帮可莉吧**
