算法第六天-删除并获得点数

删除并获得点数

题目要求

解题思路

来自[宫水三叶]
根据题意，当我们选择nums[i]的时候，比nums[i]大/小一个单位的数都不能被选择。
如果我们将数组排好序，从前往后处理，其实只需要考虑“当前数”与“前一个数”的[大小&选择]关系即可，这样处理完，显然每个数的[前一位/后一位]都会被考虑到。
这样我们将问题转化为一个[序列DP]问题（选择某个数，需要考虑前一个数的[大小/选择]状态）
定义f[i][0]代表数值为i的数字[不选择]的最大价值；f[i][1]代表数值为i的数字[选择]的最大价值。
为了方便，我们可以先将nums中出现的所有数值进行计数，而且由于数据范围$10^4$，我们可以直接使用数组cnts[]进行计数：cnts[x]=代表数值x出现了i次。
然后分别考虑一般性的f[i][0]和f[i][1]该如何计算：

• f[i][0]:当数值i不被选择，那么前一个数[可选/可不选]，在两者中取max即可。转移方程为f[i][0]=max(f[i-1][0],f[i-1][1])
• f[i][1]:当数值i被选，那么前一个数只能[不选]，同时为了总和最大数值i要选就要全部选完。转移方程为f[i][1]=f[i-1][0]+i * cnts[i]

代码

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        cnts=[0]*10009
        n = len(nums)
        m=0
        for i in nums:
            cnts[i] +=1
            m = max(m,i)
        f =[[0] * 2 for _ in range(m+1)]
        for i in range(1,m+1):
            f[i][1] = f[i-1][0] + i * cnts[i]
            f[i][0] = max(f[i-1][1],f[i-1][0])
        return max(f[m][0],f[m][1])

复杂度分析

时间复杂度：遍历nums进行计数和取最大值max，复杂度为$O(n)$；共有$max?2$个状态需要被转移，每个状态转移的复杂度为$O(1)$，整体复杂度为$O(n+max)$
空间复杂度：$O(n)$