1
题目描述
给定一个整数数组 nums ,每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数,同步删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。初始点数为0,返回可获得的最大点数。如:nums=[3,4,2],返回6。(首先选择4,积累4点数,同时删除3,再选择2,再积累2点数,总共为6。其他方式积累的点数均小于6)
2
题解
思路:动态规划
通过题目要求,首先要明确一点是:当选择了一个值获得其点数,则其他相同的值也会选择。因为当选择一个值时,相邻值已被删除,因此其他相同的值不会被删除,一定会选择到。因此可以建立一个列表value,以值作为下标,记录选择每个值时对应可获得的点数。如:[2,2,3,3,4],value[2]=2*2,value[3]=3*2,value[4]=4*1,所以最后得到value=[0,0,4,6,4]。
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
if not nums:
return 0
dp = [0]*(max(nums)+1)
value = dp.copy()
#value = [0]*(max(nums)+1)
for i,a in enumerate(nums):
value[a]+=a
dp[1] = value[1]
for i in range(2,max(nums)+1):
dp[i]=max(dp[i-1],dp[i-2]+value[i])
return dp[-1]