网站小图片素材长沙微信网站制作

当前位置： 首页 > news >正文

网站小图片素材,长沙微信网站制作,淮北论坛租房信息,24什么网站建设解锁动态规划的奥秘#xff1a;从零到精通的创新思维解析#xff08;6#xff09; 前言#xff1a; 在动态规划的众多问题中#xff0c;多状态DP问题是一个非常重要的类别。它的难点在于如何设计合适的状态表示和转移方程#xff0c;从而高效地解决问题。 多状态DP的核…解锁动态规划的奥秘从零到精通的创新思维解析6 前言 在动态规划的众多问题中多状态DP问题是一个非常重要的类别。它的难点在于如何设计合适的状态表示和转移方程从而高效地解决问题。 多状态DP的核心思想在于针对问题的不同属性或限制条件将状态表示扩展为多个维度使得状态可以更加精确地描述问题的子结构。这种方法既可以帮助我们更好地分解问题又能够在求解过程中保留更多的信息从而为最终的结果提供完整的支持。 在实际应用中多状态DP常用于解决路径规划、背包问题、字符串编辑、博弈问题等场景。例如在路径规划问题中我们可以通过增加状态的维度来描述位置、步数以及路径的某些限制条件在资源分配问题中我们可以通过扩展状态来考虑当前的资源利用率和历史决策。 本篇内容将聚焦于多状态DP问题的基本原理和解决方法结合典型实例逐步介绍从状态定义、转移方程设计到代码实现的完整过程。希望通过这一系列讲解读者能够对多状态DP的理论和实践有更深入的理解掌握其在解决实际问题时的技巧与方法。 今天小编就要开启动态规划的多状态dp问题的讲解了希望我讲完几篇文章后对屏幕后的你会有一定程度的帮助那么废话不多说开启今天的做题之旅。 文章目录 解锁动态规划的奥秘从零到精通的创新思维解析61.按摩师1.1.题目来源1.2.题目分析1.3.思路讲解1.状态表示2.状态转换方程3.初始化4.填表顺序5.返回值 1.4.代码讲解1.5.完整代码展示 2.删除并获得点数2.1.题目来源2.2.题目解析2.3.思路分析1.状态表示2.状态转换方程3.初始化4.填表顺序5.返回值 2.4.代码讲解2.5.完整代码展示 3.总结 1.按摩师 1.1.题目来源 这个题目和之前的题一样来自于力扣下面小编给出本题的链接面试题 17.16. 按摩师 - 力扣LeetCode 1.2.题目分析 本题也是比较容易读懂的虽然题干有点长但是简单的概括下其实就是一个按摩师在一天可以有两种选择分别是选择接受预约和不接受预约如果接受预约的话那么后一天就不可以在预约了因为连续两天是不可以去预约的此时我们需要在一个数列中挑选预约时间此时我们需要找到预约时间最长的集合这便是这个题目的大体下面小编进入题目的思路讲解。 1.3.思路讲解 对于动态规划的题目我们需要先设置好一个dp表之后我们就要五步走来分析问题了。 1.状态表示 对于本题的状态表示我们还是靠经验 题目分析来完成这道题目此时我们根据题意可以知道此时的dp表有这两种意思分别是接受预约和接受不预约此时如果我们光靠一个一维的dp表那还是远远不够的所以本题就需要用到两个dp表来解决问题这便是本节主要讲述的内容——多状态的dp问题此时我们需要用到两个表小编分别命名为f和g高中的f(x) 和 g(x)函数演变而来当然虽然分为了两个表但是我们的分析方法还是一样的无非就是以i位置为结尾或者开头进行分析问题此时我们让f[i]代表到达i位置时接受此预约g[i]表示达到此位置不接受此预约此时我们用了两个表分别表示了此时的状态下面我们就可以写本题目的状态转换方程。 2.状态转换方程 我们可以先求f表的状态转换方程此时我们知道了此时f表代表了什么所以此时我们知道此时的i位置已经接受了预约此时我们就可以判定i-1位置肯定是不会预约的相邻两个位置不能预约所以此时我们就可以表示出f[i]。 f[i] g[i - 1] nums[i];之后我们在判断此时的g[i]相比于f[i]g[i]就复杂了一丢丢此时我们可以把i-1分为两种情况分别是前一天预约了和前一天没预约因为此时i位置代表着不预约这就不好说明它的前一天到底是预约了还是没有预约所以此时我们需要判断一下选手判断的条件也是很简单此时我们仅需判断这两个谁最大就可以了所以此时我们用max函数便可以表示出此时的方程。 g[i] max(f[i - 1],g[i - 1]);3.初始化 此时因为初始化比较简单所以此时我们无须在添加虚拟节点了因为两个表都是第一个位置越界所以此时我们先表示它俩就好了其中的f[i]代表到达i位置的时候接受预约所以此时的f[0]自然就是nums[0]数组第一个元素同理此时的g[0]我们也可以表示为0因为当前位置不选此时我们的初始化工作便结束了。 4.填表顺序 从左到右两个表一起填。 5.返回值 返回两个表最后一个位置中最大的那个。 1.4.代码讲解 此时我们需要先创建两个表分别是f表和g表此时对两个初始位置进行初始化处理。当然此时有个特殊情况我们要讨论此时如果数组没有元素那么此时我们直接返回0就好存在一个元素就直接返回第一个位置元素即可。 int n nums.size(); //先判断特殊情况放置越界 if(n 0) return 0; if(n 1) return nums[0]; vectorint f(n); //选择 vectorint g(n); //不选择 f[0] nums[0]; g[0] 0;之后我们就根据状态转换方程进行循环填表即可此时我们需要填两个表。之后返回两个表中最大的元素即可。 for(int i 1 ; i n ; i){f[i] g[i-1] nums[i];g[i] max(g[i-1],f[i-1]);} return max(f[n-1],g[n-1]);1.5.完整代码展示 class Solution { public:int massage(vectorint nums) {int n nums.size();//先判断特殊情况放置越界if(n 0) return 0;if(n 1) return nums[0];vectorint f(n); //选择vectorint g(n); //不选择f[0] nums[0];g[0] 0;for(int i 1 ; i n ; i){f[i] g[i-1] nums[i];g[i] max(g[i-1],f[i-1]);}return max(f[n-1],g[n-1]);} };2.删除并获得点数 2.1.题目来源 本题同样来自于力扣下面小编给出链接740. 删除并获得点数 - 力扣LeetCode 2.2.题目解析 此时我们通过对题目的解读可以很容易了解题目想告诉我们的东西此时给定我们一个整数数组此时我们可以选择其中的一个数删除并获取它在数组中的所有值只不过每次我们删完以后还要直接删取它的相邻元素可以理解为相邻元素不可以选取就拿例1为例此时我们可以选择删去4并获取它的点数只不过此时我们要删掉3和5此时数组中有3所以我们要把3删掉之后在选择2以后此时我们就获得了此数组的最大点数那就是4 2 6这便是本题目想传递给我们的意思下面进入思路分析部分。 2.3.思路分析 对于本题我们可以先做一步预处理因为此时如果我们一昧的去找点数删除点数这个题目的难度系数会骤增所以为了减轻难度此时我们可以选择在开辟一个数组这个数组的功能就是为了统计数组里面某个数所有的点数简单来说就是下标是数本身里面存储的内容是在原数组该数所有和相加类似哈希表此时可以对这个新的数组来一次按摩师问题这样本题目就解决完了所以大多数小伙伴都知晓了本题目的核心就是预处理。 在预处理结束以后此时我们可以在创建两个表一个f表一个g表之后我们就可以根据动态规划的五步走来解决问题了。 1.状态表示 此时我们依靠经验 题目分析来解决本题目此时我们可以以某个位置为结尾来分析问题此时的f[i]表示到达i位置的时候选取该位置的点数g[i]表示当到达i位置的时候不选择该点数之后我们就可以进入方程的书写了。 2.状态转换方程 此时我们先分析f表此时的f表代表着到达i位置时选择该位置元素所以我们可以推断出它之前的位置是不选取点数的因为相邻点数不可以被选取所以此时的f[i]可以表示为下 f[i] g[i - 1] nums[i];之后我们再来分析g表此时的g表之前的状态可能会有两种分别是之前选了或者是之前没选此时我们选择其中的最大值作为该位置的值即可。 g[i] max(f[i - 1],g[i - 1]);3.初始化 因为此时我们新开辟的数组下标对应着点数所以此时0位置的数据自然为0因为不管有几个0加起来还是0所以此时的f表和g表第一个位置均为0即可我们在创建的时候就默认为0了。 4.填表顺序 从左到右两表一起填写。 5.返回值 此时我们返回最后一个位置两表的最大值即可。 2.4.代码讲解 此时我们先要进行预处理操作此时为了方便我们直接用给定的数组的最大值作为新数组的大小这样的话在之后的例子中就不会出现数组大小不够的情况了之后我们让新数组下标对应着的值相加即可然后创立两个新的表分别是f表和g表。 int N 10001; vectorint s(N); for(auto e: nums) s[e] e; //此时右边的数组表示一个下标对应一个数有多少的数组 vectorint f(N); vectorint g(N);之后我们循环填入数据即可此时这个步骤就不详讲了。填完后返回两表最后一个位置的最大值即可。 for(int i 1 ; i N ; i){f[i] g[i - 1] s[i];g[i] max(g[i - 1],f[i - 1]);} return max(f[N - 1],g[N - 1]);2.5.完整代码展示 class Solution { public:int deleteAndEarn(vectorint nums) {int N 10001;vectorint s(N);for(auto e: nums) s[e] e; //此时右边的数组表示一个下标对应一个数有多少的数组vectorint f(N);vectorint g(N);for(int i 1 ; i N ; i){f[i] g[i - 1] s[i];g[i] max(g[i - 1],f[i - 1]);}return max(f[N - 1],g[N - 1]);} };3.总结 本题目到这里也就完全结束了今天是小编第一次讲述多状态dp问题所以有些地方难免会出错希望读者见谅有错误可以在评论区指出我会定时看评论最近小编在期末备战我越发觉的自己越到关键玩心越大今日我又玩到了很晚匆匆的结束本篇文章希望以后的我看到这句话引以为戒一起做题的时光总是很短暂那么各位大佬们我们下一篇文章见啦