一、问题描述
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
题目链接：按摩师
二、题目要求
样例
输入： [2,7,9,3,1] 输出：12解释：选择1号预约、3号预约和5号预约，总时长=2+9+1=12。
考察
动态规划中等题型 建议用时15~30min
三、问题分析
毕竟是动态规划，还是老老实实用我们的三步走，老套路了：
第一步 含义搞懂：
按摩师在有休息间隔的情况下，如何赚取更多的钱。
那么dp[i]就代表下标0~i这段时间内，赚取的最大金额。
第二步 变量初始：
以上面的样例为例：
dp[0]=nums[0] 只有一个客人，所以只能选择这一个了dp[1]=max(nums[0],nums[1]) 当只有两个客人时，出价最高者得
第三步 规律归纳：
那么dp[i]和前面的关系如何呢？ 有两种选择：
不选择当前的客户，而是选择前一个顾客dp[i-1] 选择当前的客户，前一个顾客不能选了，要隔2个nums[i]+dp[i-2]
那么这两种选择，只要判断哪一种选择赚的钱更多不就行了，规律如下：
dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
三步走，打完收工！
四、编码实现
classSolution { public: intmassage(vector<int>&nums) { inti,n=nums.size();//初始化定义intdp[n+1]; if(n==0) return0;//没人预约if(n==1) returnnums[0];//只有一个人预约dp[0]=nums[0];//变量初始dp[1]=max(nums[0],nums[1]);//变量初始for(i=2;i<n;i++) { dp[i]=max(nums[i]+dp[i-2],dp[i-1]);//规律归纳 } returndp[n-1];//输出结果 } };
五、测试结果
