LeetCode 按摩师题解

题目描述

一个按摩师接收预约，但是不能接相邻的预约。给定预约时间，找到能获得的最长总服务时间。

示例：

输入：nums = [1,2,3,1]
输出：4

解题思路

方法：动态规划

思路：

• 使用动态规划，dp[i] 表示考虑前 i 个预约能获得的最长服务时间。
• dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

复杂度分析：

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

代码实现

def massage(nums): if not nums: return 0 if len(nums) == 1: return nums[0] prev2 = 0 prev1 = nums[0] for i in range(1, len(nums)): curr = max(prev1, prev2 + nums[i]) prev2 = prev1 prev1 = curr return prev1 # 测试 def test_massage(): nums = [1, 2, 3, 1] print(massage(nums)) # 输出：4 if __name__ == "__main__": test_massage()

总结

按摩师是动态规划的典型应用，通过维护前两个状态来计算最长服务时间。