LeetCode如何实现删除与获得点数
小编给大家分享一下LeetCode如何实现删除与获得点数,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
创新互联公司是一家集网站建设,贞丰企业网站建设,贞丰品牌网站建设,网站定制,贞丰网站建设报价,网络营销,网络优化,贞丰网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
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
题解
中间状态:此处中间状态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如何实现删除与获得点数”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!
当前题目:LeetCode如何实现删除与获得点数
网站地址:http://scyanting.com/article/gjesoj.html