解锁动态规划的奥秘：从零到精通的创新思维解析（6）
解锁动态规划的奥秘：从零到精通的创新思维解析（6）
前言：
在动态规划的众多问题中，多状态DP问题是一个非常重要的类别。它的难点在于如何设计合适的状态表示和转移方程，从而高效地解决问题。
多状态DP的核心思想在于：针对问题的不同属性或限制条件，将状态表示扩展为多个维度，使得状态可以更加精确地描述问题的子结构。这种方法既可以帮助我们更好地分解问题，又能够在求解过程中保留更多的信息，从而为最终的结果提供完整的支持。
在实际应用中，多状态DP常用于解决路径规划、背包问题、字符串编辑、博弈问题等场景。例如，在路径规划问题中，我们可以通过增加状态的维度来描述位置、步数以及路径的某些限制条件；在资源分配问题中，我们可以通过扩展状态来考虑当前的资源利用率和历史决策。
本篇内容将聚焦于多状态DP问题的基本原理和解决方法，结合典型实例，逐步介绍从状态定义、转移方程设计到代码实现的完整过程。希望通过这一系列讲解，读者能够对多状态DP的理论和实践有更深入的理解，掌握其在解决实际问题时的技巧与方法。
今天小编就要开启动态规划的多状态dp问题的讲解了，希望我讲完几篇文章后，对屏幕后的你会有一定程度的帮助，那么废话不多说，开启今天的做题之旅。
文章目录
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];
vector<int> f(n); //选择
vector<int> 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(vector<int>& nums) {
int n = nums.size();
//先判断特殊情况，放置越界
if(n == 0) return 0;
if(n == 1) return nums[0];
vector<int> f(n); //选择
vector<int> 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;
vector<int> s(N);
for(auto e: nums) s[e] += e; //此时右边的数组表示一个下标对应一个数有多少的数组
vector<int> f(N);
vector<int> 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(vector<int>& nums) {
int N = 10001;
vector<int> s(N);
for(auto e: nums) s[e] += e; //此时右边的数组表示一个下标对应一个数有多少的数组
vector<int> f(N);
vector<int> 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问题，所以有些地方难免会出错，希望读者见谅，有错误可以在评论区指出，我会定时看评论，最近小编在期末备战，我越发觉的自己越到关键玩心越大，今日我又玩到了很晚，匆匆的结束本篇文章，希望以后的我看到这句话引以为戒，一起做题的时光总是很短暂，那么各位大佬们，我们下一篇文章见啦！
原文地址：https://blog.csdn.net/effort123_/article/details/145207337
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！