?题目:https://leetcode-cn.com/problems/the-masseuse-lcci/
一个有名的按mo师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按mo师找到最优的预约集合(总预约时间最长),返回总的分钟数。
?
示例 1:
?
输入: [1,2,3,1]
输出: 4
解释: 选择 1 号预约和 3 号预约,总时长 = 1 + 3 = 4。
示例 2:
?
输入: [2,7,9,3,1]
输出: 12
解释: 选择 1 号预约、 3 号预约和 5 号预约,总时长 = 2 + 9 + 1 = 12。
示例 3:
?
输入: [2,1,4,5,3,1,1,3]
输出: 12
解释: 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约,总时长 = 2 + 4 + 3 + 3 = 12。
通过次数
?
?
解题:
定义状态
f(n)为若一共为n个预约,一定选中第n个预约的最长总预约时间(该时间非所有预约序列中的最长总预约时间,因为可以不选择第n个预约)。
那么,最长总预约时间是多少呢?一定是选中第n-1或者选中第n个预约的最长总预约时间。(无论如何选择预约,要求最长,肯定会选择最后两个中的一个预约,因为预约时长不可能为负)
?
转移方程和初始值
cost(n)代表第n个预约的时长。
n=0;f(n)=0
n=1;f(n)=cost[1]
n=2;f(n)=max(cost[1],cost[2])
n=3;f(n)=max(cost[1]+cost[3],cost[2]);
n>3;f(n)=max(f(n-3),f(n-2))+cost[n];
返回结果
ret=max(f(n-1),f(n))
?
class="java">class Solution { public int massage(int[] nums) { if(nums==null || nums.length==0){ return 0; } if(nums.length==1){ return nums[0]; } if(nums.length==2){ return Math.max(nums[0],nums[1]); } if(nums.length==3){ return Math.max(nums[0]+nums[2],nums[1]); } int a=nums[0]; int b=nums[1]; int c=nums[0]+nums[2]; int d=c; for(int i=3;i<nums.length;i++){ c=d; d=Math.max(a,b)+nums[i]; a=b; b=c; } return Math.max(c,d); } }
?
详细请看:
?https://leetcode-cn.com/problems/the-masseuse-lcci/solution/dong-tai-gui-hua-shuang-100-by-chenghuiz/
?