动态规划算法：11.简单多状态 dp 问题_按摩师_C++
目录：
题目链接：面试题 17.16. 按摩师 - 力扣（LeetCode）
题目链接：面试题 17.16. 按摩师 - 力扣（LeetCode）
一、题目解析
题目：
解析：
由题目我们可知，我们两次选择的预约时间不能相邻，并且题目要求我们最后的结果(预约时长)达到最大。
拿示例二简单举例：
两种情况：
- 选1：选1之后我们就不能选2，选3，选3之后不能选4，选5，此时结果为13
- 不选1：选2，选2之后不能选3，选4，选4之后不能选5，此时结果为10
二、算法原理
1、状态表示
我们在状态标识的时候，一般都会创建一个数组dp，也就是我们所说的dp表，我们要做的就是把每一个状态的值填入这个表内，最终这个表内的某一个值可能就是我们要返回的值。
状态简单理解就是dp表内某一个值代表的含义。
如何确定状态表示
- 题目要求
简单的题目里一般会给出
- 经验+题目要求
越学越深入，动态规划也是熟能生巧，在题目中没有明显给出的时候，我们就要凭借自己做题的经验来确定，所以就需要我们大量的做题。
- 分析问题的过程中，发现重复子问题
分析问题的过程中把重复子问题抽象成我们的状态表示，这个更难理解，一切的基础都是我们先对动态规划算法熟练运用。我也不懂，我们慢慢来。
综上：我们通常会以一个位置为结尾或者开始求得我们想要的答案
那我们的这道题得状态表示是什么样的：
根据经验，我们以一个位置为结尾做题
状态表示：dp[i]表示到达i位置时预约时长到达最大
2、状态转移方程
确定状态表示之后我们就可以根据状态标识推出状态转移方程
状态转移方程是什么？
不讲什么复杂的，简单来说状态转移方程就是 dp[i]等于什么 dp[i]=？
这个就是状态转移方程，我们要做的，就是推出dp[i]等于什么
我们根据状态表示再结合题目+经验去推理转移方程，这一步也是我们整个解题过程中最难的一步
我们在这道题先简单了解下什么是状态转移方程，之后比较难的题目再细推
状态转移方程推理：
首先，我们已经知道状态表示为dp[i]为到达i位置时预约时长到达最大值
其次，在题目中还有一个条件，就是相邻的位置不可选
那我们在此就需要对i位置的状态进行分析，我们到底是选择i还是不选i，因为选与不选都有可能使预约时长达到最大值
既然有选与不选两种状态，那么我们的状态转移方程就有两个
我们把表示选择i位置时预约时长达到最大的状态转移方程命名为f(x),把不选择i位置时预约时长达到最大的状态转移方程命名为g(x)，把原预约时长数组命名为nums
我们对i位置进行一个状态分析：
3、初始化
我们创建dp表就是为了把他填满，我们初始化是为了防止在填表的过程中越界
怎么谈越界？
我们在填f[0]（nums原数组的第一个数）时，我们选择了第一个预约时长，根据状态转移方程中我们求f[0]就需要f[-1],但我们没有f[-1]这个值，这就是越界
dp表初始化:
这里不用对dp表进行初始化
特殊位置初始化：
选择第一个位置：我们需要对f[0]赋值为原数组nums[0],这样我们就不用担心其越界
不选择第一个位置：g[0]就等于0，初始化时已经赋值为0，不用再管这个
4、填表顺序
从左到右依次填表
5、返回值
因为我们有选与不选两种状态，所以我们最后需要比较这两种状态的大小，选择最大的那一个
返回值为max(f[n],g[n]),n为最后一个位置的下标
三、编写代码
class Solution {
public:
int massage(vector<int>& nums) {
int n=nums.size();
//细节处理，当没有预约时直接返回0
if(n==0)return 0;
//两个dp状态表的建立
vector<int> f(n);
auto g=f;
//特殊位置初始化
f[0]=nums[0];
//填表
for(int i=1;i<n;i++)
{
f[i]=g[i-1]+nums[i];
g[i]=max(f[i-1],g[i-1]);
}
//返回值
return max(f[n-1],g[n-1]);
}
};原文地址：https://blog.csdn.net/2302_76267737/article/details/142526787
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！