程序员面试金典 - 面试题 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。

题目思考

1. 如何根据前一个预约情况得到当前预约情况?

解决方案

思路

• 分析题目, 对于当前预约而言, 有两种选择: 1. 接受该预约, 但需要不接上一预约; 2. 不接该预约, 那么接不接上一预约都可以
• 也就是相邻预约之间的关系非常明确, 可以尝试动态规划的思路
• 定义 dp[i][0] 为不接受当前预约情况下的最大预约时长, 而 dp[i][1] 是接受当前预约情况下的最大预约时长
• 则根据上述分析, 有如下转移方程:
  • dp[i][0]=max(dp[i-1][0], dp[i-1][1])
  • dp[i][1]=dp[i-1][0]+nums[i]
• 显然初始化为 dp[0][0]=0, 而 dp[0][1]=nums[0]
• 最终结果就是max(dp[n-1][0], dp[n-1][1])
• 另外, 注意到这里某个下标的 dp 值只与前一下标有关, 所以可以进一步优化
• 只使用两个变量 dp0 和 dp1, 然后每次转移时套用上述公式即可, 这样只需要 O(1) 空间
• 下面代码有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(N): 需要遍历整个数组一遍
• 空间复杂度 O(1): 优化后只需要几个常数空间的变量

代码

class Solution:
    def massage(self, nums: List[int]) -> int:
        # 双变量dp
        if not nums:
            # 没有预约, 返回0
            return 0
        # dp0表示不接当前预约的最长时间, dp1表示接当前预约的最长时间
        # 初始化dp1为nums[0]
        dp0, dp1 = 0, nums[0]
        for x in nums[1:]:
            # 从下标1开始遍历
            # 不接当前预约时, dp0更新为前一dp0和dp1的较大值
            # 接当前预约时, dp1只能更新为前一dp0加上当前时间, 因为不能接受相邻预约
            dp0, dp1 = max(dp1, dp0), dp0 + x
        # 最终结果就是dp0和dp1的较大值
        return max(dp0, dp1)

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊