面试题 17.16. 按摩师

题目链接：

面试题 17.16. 按摩师

题目描述：

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

题目分析：

此题与打家劫舍一样

题解：

int massage(int* nums, int numsSize) {if(numsSize == 0){                  // 判断nums是否为空return 0;}int max = -1;                       // nums不为空时，执行下面的程序int dp[numsSize];for(int i = 0; i < numsSize; i++){if(i <= 1){                     // 当i<=1时，按摩当次时能赚到最大的值dp[i] = nums[i];}else if(i == 2){               // 当i等于2时，能赚到的最大值为nums[0]+nums[2]dp[i] = nums[i] + dp[i-2];}else{                          // 当i大于2时，能赚到的最大值为dp[i-2]和dp[i-3]中的最大值加上nums[i]dp[i] = nums[i] + (dp[i-2] > dp[i-3]?dp[i-2]:dp[i-3]);}if(dp[i] > max){                // 当前位置能赚到的钱为最大值时，记录maxmax = dp[i];}}return max;                         // 返回max
}