题目难度: 简单
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
-
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
-
注意：本题相对原题稍作改动
示例 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. 接受该预约, 但需要不接上一预约; 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)
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号