LeetCode每日一题：3.23按摩师（八十一）

按摩师

一、LeetCode题解

瞧一瞧～

• 博健的LeetCode题解：Gitbook版本传送门
• 博健的LeetCode题解：CSDN传送门
• 有趣的CSS：Gitbook传送门
• 前端进阶笔记：Gitbook传送门

二、算法题

题目

示例

解法一 （动态规划）

• 时间复杂度：O(n)
• 空间复杂度：O(1)

思路

核心思想：dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])

1. 定义arr[i]表示前第i个预约，记录第i个预约的时长
2. 接预约之前，都会保留当前最优解

代码

• 第一版利用数组记录每一部分数据

var massage = function(nums) {
    var len = nums.length
    if(!len) return 0;
    if(len === 1) return nums[0];
    
    var arr = []
    arr[0] = nums[0]
    arr[1] = nums[0] > nums[1] ? nums[0] : nums[1]
    for(let i = 2; i < len; i++){
        arr[i] = Math.max(arr[i-1], arr[i-2]+nums[i])
    }
    return arr[len-1]
};

• 第二版直接保存最优解

var massage = function(nums) {
    var a = 0, b = 0

    for(let i = 0; i < nums.length; i++){
        let c = Math.max(b, nums[i]+a)
        a = b
        b = c
    }
    return b
};

结果