当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.程序员面试金典.1716.Masseuse 按摩师

LeetCode.程序员面试金典.1716.Masseuse 按摩师


题目描述

《程序员面试金典(第 6 版)》面试题 17.16. 按摩师
https://leetcode-cn.com/problems/the-masseuse-lcci/

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

注意:本题相对原题稍作改动

示例 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。

解题过程

相似题目
198 打家劫舍
https://leetcode-cn.com/problems/house-robber/

LeetCode.程序员面试金典.1716.Masseuse 按摩师

一开始没什么想法,感觉选择哪个数无法直接决策,偶然扫了眼题解有动态规划,自己想出来递推公式了,这还是我第一次自己把动态规划的递推公式推导出来。
做完看题解,我的想法和官方题解一样,都是用两个dp数组,其实不需要两个数组做记录,一个就够了。

动态规划1-双dp数组

include[i] 表示 nums[0…i] 中包含 nums[i] 在内的最大值
exclude[i] 表示 nums[0…i] 中不包含 nums[i] 在内的最大值

include[i] 选中 nums[i] 的话,由于不能连续 nums[i-1] 肯定无法选中
exclude[i] 不选 nums[i] 的话,有两种方案,一个是 nums[i-1] 也不选,一个是 选择 nums[i-1],取两者中的最大值即可

则有递推公式:

$ include[i] = exclude[i - 1] + nums[i] \tag{1} $
$ exclude[i] = max(exclude[i - 1], include[i - 1]) \tag{2} $

且初始条件为
include[0] = nums[0]
exclude[0] = 0

i 从前往后遍历,最后 include[n-1] 和 exclude[n-1] 两者中的最大值就是结果。

时间复杂度 O(n), 空间复杂度 O(N)

private static class SolutionV2020 {
    public int massage(int[] nums) {
        if (null == nums || 0 == nums.length) {
            return 0;
        }
        // include[i]: nums[0...i] 中包含 nums[i] 在内的最大值
        int[] include = new int[nums.length];
        // exclude[i]: nums[0...i] 中不包含 nums[i] 在内的最大值
        int[] exclude = new int[nums.length];
        include[0] = nums[0];
        int max = nums[0]; // 全局最大值

        for (int i = 1; i < nums.length; i++) {
            include[i] = exclude[i - 1] + nums[i];
            exclude[i] = Math.max(include[i - 1], exclude[i - 1]);
            max = Math.max(max, Math.max(include[i], exclude[i]));
        }
        return max;
    }
}

动态规划2-单dp数组

f[i] 表示从预约序列 nums[0…i] 中能获得的时长最大值, 则对于第 i 个数来说有两种选择,选他或者不选他,选 i 后就肯定不能选 i-1,不选 i 则可以选择 i-1
所以有递推公式:

$ f[i] = max(f[i-2] + nums[i], f[i-1]) $


GitHub代码

algorithms/leetcode/crack/_1716_Masseuse.java
https://github.com/masikkk/algorithms/blob/master/leetcode/crack/_1716_Masseuse.java


上一篇 LeetCode.146.LRU Cache 实现LRU缓存

下一篇 LeetCode.876.Middle of the Linked List 链表的中间结点

阅读
评论
803
阅读预计3分钟
创建日期 2020-03-24
修改日期 2020-03-24
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论