题目描述
这是 LeetCode 上的 740. 删除并获得点数 ，难度为 中等。
Tag : 「序列 DP」
给你一个整数数组 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 * 10410^4104
- 1 <= nums[i] <= 10410^4104
动态规划
根据题意，当我们选择 nums[i]nums[i]nums[i] 的时候，比 nums[i]nums[i]nums[i] 大/小 一个单位的数都不能被选择。
如果我们将数组排好序，从前往后处理，其实只需要考虑“当前数”与“前一个数”的「大小 & 选择」关系即可，这样处理完，显然每个数的「前一位/后一位」都会被考虑到。
这样我们将问题转化为一个「序列 DP」问题（选择某个数，需要考虑前一个数的「大小/选择」状态）。
定义 f[i][0]f[i][0]f[i][0] 代表数值为 iii 的数字「不选择」的最大价值；f[i][1]f[i][1]f[i][1] 代表数值为 iii 的数字「选择」的最大价值。
为了方便，我们可以先对 numsnumsnums 中出现的所有数值进行计数，而且由于数据范围只有 10410^4104，我们可以直接使用数组 cnts[]cnts[]cnts[] 进行计数：
cnts[x]=icnts[x] = icnts[x]=i 代表数值 xxx 出现了 iii 次。
然后分别考虑一般性的 f[i][0]f[i][0]f[i][0] 和 f[i][1]f[i][1]f[i][1] 该如何计算：
- f[i][0]f[i][0]f[i][0]：当数值 iii 不被选择，那么前一个数「可选/可不选」，在两者中取 maxmaxmax 即可。转移方程为 f[i][0]=max(f[i−1][0],f[i−1][1])f[i][0] = \max(f[i - 1][0], f[i - 1][1])f[i][0]=max(f[i−1][0],f[i−1][1])
- f[i][1]f[i][1]f[i][1]：当数值 iii 被选，那么前一个数只能「不选」，同时为了总和最大数值 iii 要选就全部选完。转移方程为 f[i][1]=f[i−1][0]+i∗cnts[i]f[i][1] = f[i - 1][0] + i * cnts[i]f[i][1]=f[i−1][0]+i∗cnts[i]
代码：
class Solution { int[] cnts = new int[10009]; public int deleteAndEarn(int[] nums) { int n = nums.length; int max = 0; for (int x : nums) { cnts[x]++; max = Math.max(max, x); } // f[i][0] 代表「不选」数值 i；f[i][1] 代表「选择」数值 i int[][] f = new int[max + 1][2]; for (int i = 1; i <= max; i++) { f[i][1] = f[i - 1][0] + i * cnts[i]; f[i][0] = Math.max(f[i - 1][1], f[i - 1][0]); } return Math.max(f[max][0], f[max][1]); } } 复制代码
- 时间复杂度：遍历 numsnumsnums 进行计数和取最大值 maxmaxmax，复杂度为 O(n)O(n)O(n)；共有 max∗2max * 2max∗2 个状态需要被转移，每个状态转移的复杂度为 O(1)O(1)O(1)。整体复杂度为 O(n+max)O(n + max)O(n+max)。
- 空间复杂度：O(n)O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.740 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
