面试题 17.16. 按摩师leetcode

1问题描述

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]

题解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