1. 题目描述

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

示例 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）
链接：https://leetcode-cn.com/problems/the-masseuse-lcci

2. 解题思路

动态规划做这道题再合适不过了，动态规划实际上就是穷举，并且穷举的同时可以把问题分解为子问题，不过同一般穷举比较来看，动态规划使用了DP Table达到了备忘录的作用，能够记录之前可能穷举过的值，尽量避免子问题之间的交叉计算，提高性能。
做动态规划的题的一般思路是先明确状态，状态是我们要解决的问题或者子问题里面变化的量，比如这道题里面，预约人数以及每次预约的时长都是定好了的，所以唯一的变量就是接受多少个预订，那么预订时长就是预订个数对应的时长相加，正好是这道题需要求解的答案；然后是定义DP Table的含义，然后再确定行为，然后明确base case，这样状态转移方程就写出来了。
比如，这道题我们确定时长为状态，然后定义dp[i]为有i个预订的情况下最长预约时长，然后定义行为有接受第i次预订和不接受，base case为dp[0]为0，dp[1]为第一个预订的时长，状态转移方程为dp[i]=max(dp[i-1], dp[i-2]+nums[2])，即在有i个预订的情况下，最长预约时长为如果接受第i个预订，那么时长为dp[i-2]+nums[2]，不接受为(dp[i-1]。

2.1 代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var massage = function(nums) {
    const len = nums.length
    if (len === 0) return 0
    if (len === 1) return nums[0]
    const dp = new Array(len)
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for (let i = 2; i < len; i++) {
        if (dp[i]) continue
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
    }
    return dp[len-1]
};

2.2 性能表现

image.png