按摩师问题-双一百解法 博客分类： 算法题 按摩师问题按摩师动态规划Java
程序员文章站
2024-03-18 09:24:52
...
题目：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 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);
}
}
详细请看：