面试题 17.16. 按摩师 (动态规划easy)

面试题 17.16. 按摩师 (动态规划easy)

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

class Solution {
public:int massage(vector<int>& nums) {//leetcode老是出这种边界情况，一定要注意。if(nums.size()==0){return 0;}if(nums.size()==1){return nums[0];}nums[1]=max(nums[1],nums[0]);//主要考察状态转移方程的构造，其实是找问题本质的规律for(int i =2;i<nums.size();i++){nums[i]=max(nums[i-1],nums[i-2]+nums[i]);}//max_element函数返回的是迭代器，所以记得加上*return *max_element(nums.begin(),d());}
};

上面是为了简便（偷懒）才这样写，其实新建一个数组dp[]，代码更加可读一点。
算了不偷懒了

例如下面：

class Solution {
public:int massage(vector<int>& nums) {if(nums.size()==0){return 0;}if(nums.size()==1){return nums[0];}vector<int> dp(nums.size(),0);dp[0]=nums[0];dp[1]=max(nums[1],nums[0]);for(int i =2;i<nums.size();i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}return *max_element(dp.begin(),dp.end());}
};

思路：dp[ i ]作为一个状态，指示从第一天到第i天允许的最大总预约分钟数。dp[ i ]取决于 （截止一天前的预约最大总分钟数 ， 截止两天前的预约的最大预约总分钟数+第i天预约分钟数） 的最大值 ，（因为不能连续预约嘛），转换为状态转移方程就是max(dp[i-1],dp[i-2]+nums[i])

动态方程难点在于找出问题本质，构造状态转移方程。

另外，一般来说，边界都是不符合状态转移方程的，手动配置即可。例如该题的dp[0],dp[1]按实际情况手动输入即可。