「LeetCode每日一题」——LCCI.17.16. 按摩师
LCCI.17.16. 按摩师
链接：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。
思路
本题输入为长度为n的数组，表示n个预约，求n个预约最大的时长。
如果我们接受了第n个预约，那我们就不能接受相邻的，dp[n]=dp[n-2]+nums[n]
如果我们不接受第n个预约，那么dp[n]=d[n-1]
状态转移方程： dp[i] = max(dp[i-1],dp[i-2]+nums[i])
方案代码
解决方案：
class Solution:
def massage(self, nums: List[int]) -> int:
n=len(nums)
if n==0:
return 0;
a,b=0,nums[0]
for i in range(1,n):
a,b=max(a,b),a+nums[i]
return max(a,b)原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/252.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」——121. 买卖股票的最佳时机
121. 买卖股票的最佳时机 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/难度：简单 题…
-
「LeetCode每日一题」—— 23. 合并K个排序链表
23. 合并K个排序链表 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/难度：中等 题目 点击原文链接跳转查看题…
-
「LeetCode每日一题」—— LCCI.16.03.交点
LCCI.16.03.交点 链接：https://leetcode-cn.com/problems/intersection-lcci/难度：困难 题目 点击原文链接跳转查看题目 …
-
「LeetCode每日一题」——LCOF.62. 圆圈中最后剩下的数字
LCOF.62. 圆圈中最后剩下的数字 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-…
-
「LeetCode每日一题」——695. 岛屿的最大面积
695. 岛屿的最大面积 链接：https://leetcode-cn.com/problems/max-area-of-island/难度：中等 题目 给定一个包含了一些 0 和…
-
「LeetCode每日一题」—— 887. 鸡蛋掉落
887. 鸡蛋掉落 链接：https://leetcode-cn.com/problems/super-egg-drop/难度：难度 题目 你将获得 K 个鸡蛋…
-
「LeetCode每日一题」——1013. 将数组分成和相等的三个部分
1013. 将数组分成和相等的三个部分 链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-w…
-
「LeetCode每日一题」——999. 车的可用捕获量
999. 车的可用捕获量 链接：https://leetcode-cn.com/problems/available-captures-for-rook/难度：简单 题目 在一个 …
-
「LeetCode每日一题」——892. 三维形体的表面积
892. 三维形体的表面积 链接：https://leetcode-cn.com/problems/surface-area-of-3d-shapes/难度：简单 题目 在&nbs…
-
「LeetCode每日一题」——LCOF.57 – II. 和为s的连续正数序列
面试题57 – II. 和为s的连续正数序列 链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu…
您必须登录才能发表评论。