详解为何能转换成「序列 DP」问题求解

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 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 * $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]);
    }
}
复制代码