LC 740. 删除并获得点数

题目描述

这是 LeetCode 上的 740. 删除并获得点数 ，难度为 中等。

给你一个整数数组 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^4$
• 1 <= nums[i] <= $10^4$

---

动态规划

根据题意，当我们选择 $nums[i]$ 的时候，比 $nums[i]$ 大/小 一个单位的数都不能被选择。

如果我们将数组排好序，从前往后处理，其实只需要考虑“当前数”与“前一个数”的「大小 & 选择」关系即可，这样处理完，显然每个数的「前一位/后一位」都会被考虑到。

这样我们将问题转化为一个「序列 DP」问题（选择某个数，需要考虑前一个数的「大小/选择」状态）。

定义 $f[i][0]$ 代表数值为 $i$ 的数字「不选择」的最大价值；$f[i][1]$ 代表数值为 $i$ 的数字「选择」的最大价值。

为了方便，我们可以先对 $nums$ 中出现的所有数值进行计数，而且由于数据范围只有 $10^4$，我们可以直接使用数组 $cnts[]$ 进行计数：$cnts[x] = i$ 代表数值 $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 {
    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]);
    }
}

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

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.740 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。