蓝桥杯每日一练——按摩师
按摩师
https://leetcode-cn.com/problems/the-masseuse-lcci/
题目描述：
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
思路分析：
这是一道典型的动态规划一维数组题目，当只有一个顾客的时候，我们不得不选，return num[0],当有两个顾客的时候，我们可以选择第一个顾客和第二个顾客当中的较大值，并且更新num[1](也就是两个顾客时最优子结构) ，当出现第三个顾客时，我们可以选择第一个顾客加上第三个顾客，也可以选择第二个顾客，所以需要比较这两个方案，注意我们为什么这么做，我们不可能只选择第三个顾客，因为第一个顾客肯定给钱，不赚白不赚，所以我们也就直到了公式，并且更新数组，数组中最后一个数据就是我们的答案。另外，我看到有网友的答案当中开辟了dp辅助数组，其实这种方式是完全没有必要的，我们不需要以前的数据，更新当前的数组即可。
C++实现：
public: int massage(vector& nums) { int size = nums.size(); if(size == 0) return 0; if(size == 1) return nums[0]; nums[1] = max(nums[0],nums[1]); for(int i = 2; i < size; i++){ nums[i] = max(nums[i-2]+nums[i],nums[i-1]); } return nums[size - 1]; }};
