给你一个整数数组 nums ,你可以对它进行一些操作。每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
主要思路:其实这道题是打家劫舍的变种,使用动态规划求解
详细思路:这道题的关键在于选择了一个数那么数组中其他相同的数也相当于被选择了,题目中说x-1和x+1不能选择,就相当于打家劫舍中的相邻人家不能抢。
- 创立一个total数组,长度为max(nums)+1,将nums[i]存储的total[nums[i]]中,那么最后total里面存储的就是选择这个数可以获得的点数。
- 利用打家劫舍的方法进行求解,状态转移方程为 dp[i] = max(dp[i-2]+nums[i], dp[i-1])或者使用双变量节省空间**first, second = second, max(second, first + total[i]) 最后return second
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
max_num = max(nums)
total = [0] * (max_num+1)
for val in nums:
total[val] += val
def rob(ls:List[int])->int:
first = ls[0]
second = ls[1]
for i in range(2, len(ls)):
first, second = second, max(second, first+ls[i])
return second
return rob(total)
做了好几道动态规划的题目了,还是他妈的不会
标签:740,删除,nums,max,second,ls,点数,total,first From: https://www.cnblogs.com/zhumeili/p/18091392