题目描述
给你一个整数数组 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 * 10^41 <= nums[i] <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-and-earn
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
动态规划
首先分析一下题目中的操作，只要选择了某个数字 num，在获得删除它并获得相应的分值之后，同时会删除数组中的所有 num - 1 以及 num + 1。为了保证得分最高，对于剩下来的那些 num，必须要把它们选完，而且在后续选择过程中，不用删除 num - 1 以及 num + 1，因为在第一次操作过程中已经删除完了。
所以对于某个数字 num，如果要选择它，那么对应的最大分值就是 num * c，其中 c 为 num 在 nums 数组中出现的次数。在 Python 语言中，可以借助 collections.Counter 来轻松完成计数工作，它本质上是一个字典。
另外，数组中元素顺序对于结果没有影响，如果我们按照从小到大的顺序考虑某个数字 num 选或者不选，那么不需要考虑 num + 1，因为在升序条件下， num + 1 还未出现。
对于数组中没有出现过的数字，为了应用状态转移方程，可以考虑成出现为 0 次，这样就不算分了。这与 collections.Counter 的工作方式一致，如果访问 Counter 中不存在的元素，会返回 0，而不会抛出 KeyError 异常。
状态定义：f[i] 为数组中数字 1 ~ i 通过操作能获取的最大分值。
状态转移：
- 对于数字
i，如果选（即删除并获取分值），得分为f[i - 2] + i * c[i] - 对于数字
i，如果不选（即放弃操作），的氛围f[i - 1] - 两者取最大即可
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
from collections import Counter
c = Counter(nums)
n = max(c.keys()) + 1
f = [0, c[1]] + [0] * (n - 1)
for i in range(2, n + 1):
f[i] = max(f[i - 1], f[i - 2] + c[i] * i)
return f[-1]
运行结果：
执行结果：通过
执行用时：44 ms, 在所有 Python3 提交中击败了71.78% 的用户
内存消耗：14.8 MB, 在所有 Python3 提交中击败了96.53% 的用户
因为每个新状态只需要记录前两个状态就可以完成状态转移，所以可以使用两个变量代替 f 数组。
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
from collections import Counter
c = Counter(nums)
n = max(c.keys()) + 1
pre = 0
cur = c[1]
for i in range(2, n + 1):
pre, cur = cur, max(cur, pre + c[i] * i)
return cur
运行结果：
执行结果：通过
执行用时：52 ms, 在所有 Python3 提交中击败了31.19% 的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了61.63% 的用户
下面是 JavaScript 版本的代码：
/**
* @param {number[]} nums
* @return {number}
*/
var deleteAndEarn = function(nums) {
const max = Math.max(...nums)
const scores = new Array(max + 1).fill(0)
nums.map(num => scores[num] += num)
let pre = 0, cur = scores[1], tmp
for (let i = 2; i < scores.length; i++) {
tmp = cur
cur = Math.max(cur, pre + scores[i])
pre = tmp
}
return cur
};
运行结果：
执行结果：通过
执行用时：88 ms, 在所有 JavaScript 提交中击败了75.00% 的用户
内存消耗：39.2 MB, 在所有 JavaScript 提交中击败了83.33% 的用户
