【每日打卡】[程序员面试宝典]17.16-按摩师

马谦马谦马谦 数据结构和算法评论440字数 699阅读2分19秒阅读模式

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/the-masseuse-lcci

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

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

注意:本题相对原题稍作改动

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

二、题解

这道题目和198-打家劫舍几乎完全一样,思路也完全一样,代码都不用做太多更改。

思路:对于第i个用户,有2种策略选择,预约或不预约。

  • 如果预约,那么说明上一个用户不能预约,只能取上上个用户的最优解加上当前用户的预约时长。
  • 如果不预约,最优解就是上一个用户的最优解。

总结出来的状态转移(递推)方程:

\(dp[i] = max(dp[i-1], dp[i-2]+nums[i]])\)

三、代码实现

单元测试:

头一回打败全部打败100%(其实是新题提交的人太少了):

【每日打卡】[程序员面试宝典]17.16-按摩师

 
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2020年3月24日22:27:32
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/leetcode-the-masseuse-lcci.html
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证