按摩师问题-双一百解法

 题目：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);
    }
}

 

详细请看：

 https://leetcode-cn.com/problems/the-masseuse-lcci/solution/dong-tai-gui-hua-shuang-100-by-chenghuiz/