面试题 17.16. 按摩师

面试题 17.16. 按摩师

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
 示例 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. 打家劫舍。
动态规划题：

1. 当没有订单时，返回 0
2. 当只有一个订单时，返回当前订单时间
3. 当有两个订单时，返回时间长的订单时间
4. 当大于两个订单时，当为第 k 个时：
   1. 如果当前单接，时间为当前单时间加上 k-2 个前的最长时间
   2. 如果当前单不接，时间为 k-1 个前最长的时间

得到的递推公式为dp[i]=max(dp[i−2]+nums[i],dp[i−1])。
可以看到只和当前数的前两个数有关，可以省去 dp 的数组空间。使用 first 和 second 分别记录第 k-2 个数和第 k-1 个数，计算完max(second,first+num)后，将 first 设为 second，second 设为较大的那一方。

解答

/**
 * @param {number[]} nums
 * @return {number}
 */
var massage = function (nums) {
  let first = 0,
    second = 0;
  for (const num of nums) {
    const temp = Math.max(second, first + num);
    first = second;
    second = temp;
  }
  return Math.max(first, second);
};