欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

面试题 17.16. 按摩师leetcode

程序员文章站 2024-03-15 10:34:29
...

1问题描述

面试题 17.16. 按摩师leetcode

2题解-动态规划

这里第一瞬间想到的问题是之间做的leetcide300题最长上升子序列,用一次循环O(n)的复杂度解决了问题。

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

面试题 17.16. 按摩师leetcode
面试题 17.16. 按摩师leetcode

题解2-中间变量

方法相同

class Solution:
    def massage(self, nums: List[int]) -> int:
        first=0
        second=0
        if len(nums)==0:
            return 0
        for i in range(len(nums)):
             third=max(first+nums[i],second)
             first=second
             second=third
        return second

面试题 17.16. 按摩师leetcode

相关标签: leetcode