难度: Medium
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2] 输出：6 解释： 删除 4 获得 4 个点数，因此 3 也被删除。 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4] 输出：9 解释： 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。 总共获得 9 个点数。
提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104运行时间: 36 ms
内存: 17.7 MB
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
max_num = max(nums)
if len(nums) < 2:
return max_num
if max_num < 2:
return nums.count(1)
vec = [0 for _ in range(max_num+1)]
for i in nums:
vec[i] += 1
dp = [None for _ in range(max_num+1)]
dp[0] = vec[0]
dp[1] = max(vec[1],vec[0])
for i,d in enumerate(dp):
if i < 2:
continue
dp[i] = max(dp[i-1],dp[i-2]+vec[i]*i)
print(dp)
return dp[-1]
该题解使用动态规划的思路来解决问题。首先统计每个数字出现的次数，存储在 vec 数组中。然后创建一个 dp 数组，其中 dp[i] 表示考虑前 i 个数字时可以获得的最大点数。对于每个数字 i，可以选择删除它并获得 vec[i]*i 的点数，或者不删除它。如果删除它，那么就不能删除 i-1，此时的最大点数为 dp[i-2]+vec[i]*i；如果不删除它，那么最大点数为 dp[i-1]。最后返回 dp 数组的最后一个元素即为最大获得点数。
时间复杂度: O(n+m)
空间复杂度: O(m)
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
max_num = max(nums)
if len(nums) < 2:
return max_num
if max_num < 2:
return nums.count(1)
# 统计每个数出现的次数
vec = [0 for _ in range(max_num+1)]
for i in nums:
vec[i] += 1
# 初始化 dp 数组
dp = [None for _ in range(max_num+1)]
dp[0] = vec[0]
dp[1] = max(vec[1],vec[0])
# 填写 dp 数组
for i,d in enumerate(dp):
if i < 2:
continue
dp[i] = max(dp[i-1], dp[i-2]+vec[i]*i)
print(dp)
return dp[-1]
在动态规划解法中，数组`vec`的长度由输入数组`nums`中的最大值`max_num`确定，长度为`max_num+1`，这样可以用每个索引i直接表示数字i，方便统计每个数字出现的次数。数组`vec`的每个元素初始化为0，表示开始时每个数字出现次数为0。数组`dp`的长度同样为`max_num+1`，其用于存储到当前数字为止能获得的最大点数。`dp[0]`初始化为`vec[0]`，因为如果只有数字0，只能获得0点，`dp[1]`为`max(vec[1], vec[0])`，表示考虑数字0和1时的最优决策。
选择`dp[i-2] + vec[i] * i`作为状态转移的一种可能，是因为如果选择删除数字i，按题目规则，数字i-1不能被删除。因此，对于数字i的最优选择需要考虑在不包括i-1的情况下，即`dp[i-2]`的基础上加上通过删除所有的数字i获得的点数，即`vec[i] * i`。这种选择确保了删除数字i时，不违反题目中的删除规则，同时使得得分最大化。
`dp[1] = max(vec[1], vec[0])`表示在只考虑数字0和1时的最优选择。这里的逻辑是，如果选择删除数字1，就不能删除数字0，反之亦然。因此，`dp[1]`应该取这两种选择的最大值，即删除0获得的点数`vec[0]`和删除1获得的点数`vec[1]`中的较大者。如果设置为`vec[1] + vec[0]`，则违反了题目的删除规则，即不能同时删除相邻的数字。
这里的逻辑是基于数组`nums`中的最大值`max_num`来考虑的。如果`max_num < 2`，可能的情况只有数字0和1。若`max_num`为0，则数组中只有数字0，最大点数为0。若`max_num`为1，则数组中可能有数字0和1，但最大点数来源于所有的1，即`nums.count(1)`。因此，这个逻辑只适用于`max_num`为1的情况，而不是所有小于2的情况。对于`max_num`为0的情况，应该直接返回0。