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。

---

相似题目

LeetCode.198.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]
exclude[i] = max(exclude[i - 1], include[i - 1])

且初始条件为
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

---