本站消息

  本站每日ip已达10000,出租广告位,位置价格可谈,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-03(54)

2020-04(62)

2020-05(24)

Leetcode 面试题 17.16.按摩师

发布于2020-03-25 10:15     阅读(1044)     评论(0)     点赞(8)     收藏(4)


Leetcode 面试题 17.16.按摩师

1 题目描述(Leetcode题目链接

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

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

输入: [1,2,3,1]
输出: 4
解释: 选择 1 号预约和 3 号预约,总时长 = 1 + 3 = 4
输入: [2,7,9,3,1]
输出: 12
解释: 选择 1 号预约、 3 号预约和 5 号预约,总时长 = 2 + 9 + 1 = 12
输入: [2,1,4,5,3,1,1,3]
输出: 12
解释: 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约,总时长 = 2 + 4 + 3 + 3 = 12

2 题解

  动态规划问题,设dp[i] dp[i]表示前i i天的最优预约集合的分钟总数,则状态转移方程为:
dp[i]=max(dp[i1],dp[i2]+nums[i]) dp[i]=max(dp[i-1], dp[i-2]+nums[i])

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

原文链接:https://blog.csdn.net/qq_39378221/article/details/105064167



所属网站分类: 技术文章 > 博客

作者:一切都会好起来over

链接: https://www.pythonheidong.com/blog/article/281946/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

8 0
收藏该文
已收藏

评论内容:(最多支持255个字符)