题目描述：一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
这个题目没有思路，查阅了答案，答案是用动态规划来解
先学习一下动态规划
转自大佬的博客[https://www.cnblogs.com/hithongming/p/9229871.html]
大体明白了，动态规划就是可以根据前面的问题解来解决后面的，是有记忆性的。
典型的问题是斐波那契数列。
对于这个问题，可以有连个数组来记录。
dp[i][0]表示第i个预约没有接受时，当前的总预约时间，
dp[i][1]表示第i个预约接受时，当前的总预约时间。
所以有：
dp[i][0]=max(dp[i-1][0],dp[i-1][1])；//因为i个预约不被接受，所以前一个预约接不接受都可以
dp[i][1]=dp[i-1][1]+nums[i];//第i个被接受，所以只需要i-1个接受时的总时间+第i个的时间
可以看到，只需要dp[i-1][0]和dp[i-1][1]
所以就必要使用数组，可以直接用连个变量来代替，front_dp0,front_dp1
具体leetcode代码(有小问题，正确代码在后面)：
int massage(vector<int>& nums) {
int dp0, dp1;//dp0时不被接受，dp1被接受
int front_dp0 = 0, front_dp1 = nums[0];//表示前一个的接受和不接受
for (int i = 1; i < nums.size(); i++)
{
dp0 = max(front_dp0, front_dp1);
dp1 = front_dp0 + nums[i];
front_dp0 = dp0;
front_dp1 = dp1;
}
return max(dp0, dp1);
}
小插曲：
int front_dp0 = 0, front_dp1 = max(nums[0],nums[1]);//表示前一个的接受和不接受
for (int i = 2; i < nums.size(); i++)
{……}
提交的时候出错：
这样是不正确的，因为在循环外面给front_dp1找出第一个值的时，dp0也应该给相应的值
查找原因是因为当输入为空的时候，没有返回值，而且在使用nums[0]之前没有进行判断是否为空
在前面加一句
if(nums.empt())
return 0;
还有一个错误，只有一个数的时候出错比如[2]，应该输出2，但却是0.
原因是只有一个数，无法进入循环，而dp0和dp1还没有赋值，进入循环前加入
dp0=0;
dp1=nums[0];
正确代码：
class Solution {
public:
int massage(vector<int>& nums) {
int dp0=0, dp1=0;//dp0时不被接受，dp1被接受
if(nums.empty()) return 0;
int front_dp0 = 0, front_dp1 = nums[0];//表示前一个的接受和不接受
dp0=0;
dp1=nums[0];
for (int i = 1; i < nums.size(); i++)
{
dp0 = max(front_dp0, front_dp1);
dp1 = front_dp0 + nums[i];
front_dp0 = dp0;
front_dp1 = dp1;
}
return max(dp0, dp1);
}
};
