导航：首页 > 互联网科技 >

LeetCode如何实现删除与获得点数

发表于：2024-11-17 作者：千家信息网编辑

千家信息网最后更新 2024年11月17日，小编给大家分享一下LeetCode如何实现删除与获得点数，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！1题目描述给定一个整

千家信息网最后更新 2024年11月17日LeetCode如何实现删除与获得点数

小编给大家分享一下LeetCode如何实现删除与获得点数，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

题目描述

给定一个整数数组 nums ，每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数，同步删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。初始点数为0，返回可获得的最大点数。如：nums=[3,4,2]，返回6。（首先选择4，积累4点数，同时删除3，再选择2，再积累2点数，总共为6。其他方式积累的点数均小于6）

题解

思路：动态规划

通过题目要求，首先要明确一点是：当选择了一个值获得其点数，则其他相同的值也会选择。因为当选择一个值时，相邻值已被删除，因此其他相同的值不会被删除，一定会选择到。因此可以建立一个列表value，以值作为下标，记录选择每个值时对应可获得的点数。如：[2,2,3,3,4]，value[2]=2*2，value[3]=3*2，value[4]=4*1，所以最后得到value=[0,0,4,6,4]。

中间状态：此处中间状态dp[i]表示从1选择到i可获得的最大点数。
状态转移：一个值在整个过程中只有被删除和被获取点数两个可能，并且获取与否会影响其他数值的被选择情况。因此新来一个数，要么不选，则此时dp[i]=dp[i-1]；如果选，则i-1就不能选，此时dp[i]=dp[i-2]+value[i]，所以最终dp[i]=max(dp[i-1],dp[i-2]+value[i])。

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]

以上是"LeetCode如何实现删除与获得点数"这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！

很赞哦！