按摩师预约优化：最大化预约时间 - Python 实现

按摩师预约优化：最大化预约时间 - Python 实现

给定一个按摩师的预约请求序列，每个预约可以选择接或不接，但相邻预约需要休息时间。找出最佳预约组合，最大化总预约时间。

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

示例 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。

Python 实现：

class Solution:
    def massage(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[-1]

算法解释： 该问题可以使用动态规划来解决。我们定义 dp[i] 表示考虑前 i 个预约时，所能获得的最大总预约时间。

• 当 i == 0 时，dp[0] = nums[0]，即只有第一个预约可以接受。
• 当 i == 1 时，dp[1] = max(nums[0], nums[1])，即可以接受第一个预约，也可以接受第二个预约。
• 当 i >= 2 时，dp[i] 有两种选择：
  • 不接受第 i 个预约，则 dp[i] = dp[i-1]；
  • 接受第 i 个预约，则 dp[i] = dp[i-2] + nums[i]。

最终返回 dp[-1]，即考虑所有预约后所能获得的最大总预约时间。

总结： 本文介绍了按摩师预约优化问题，并使用动态规划方法给出了 Python 实现。该算法可以有效地求解该问题，并提供了一种思路来解决类似的预约优化问题。