按摩师问题-双一百解法_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 按摩师问题-双一百解法

按摩师问题-双一百解法

 2020/6/18 15:46:12  ChenghuiZ  程序员俱乐部  我要评论(0)
  • 摘要:题目: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号预约
  • 标签:问题

?题目: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/

?

发表评论
用户名: 匿名