面试题 17.16. 按摩师leetcode
程序员文章站
2024-03-15 10:34:29
...
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