05 August 2008
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
1
2
3
4
5
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
1
2
3
4
5
6
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
提示：
1
2
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104
先明确一个概念，就是每个位置上的数字是可以在两种前结果之上进行选择的：
如果不删除当前位置的数字，那么得到就是前一个数字的位置的最优结果。
如果当前的位置数字i需要被删，那么就会得到i - 2位置的那个最优结果加上当前位置的数字乘以个数。
以上两个结果，你每次取最大的，记录下来，然后答案就是最后那个数字了。
如果到现在有点迷糊，那么先把数字进行整理一下：
在原来的 nums 的基础上构造一个临时的数组 all，这个数组，以元素的值来做下标，下标对应的元素是原来的元素的个数。
举个例子：
nums = [2, 2, 3, 3, 3, 4]
构造后（值为0的0个，值为1的0个，值为2的2个。。。）：
all=[0, 0, 2, 3, 1];
就是代表着 2 的个数有两个，3 的个数有 3 个，4 的个数有 1 个。
这样就可以变成打家劫舍的问题了。
打家劫舍的最优子结构的公式：
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
再来看看现在对这个问题的最优子结构公式：
dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * all[i]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public int deleteAndEarn(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
if (len == 1) {
return nums[0];
}
// 找到数组中出现的最大值
int max = Arrays.stream(nums).max().getAsInt();
// all[0] 表示0出现的次数
int[] all = new int[max + 1];
for (int num : nums) { // 统计某值出现了多少次
all[num]++;
}
// dp[0] 表示0位置的最大值
int[] dp = new int[max + 1];
dp[1] = 1 * all[1];
dp[2] = Math.max(dp[1], 2 * dp[2]);
for (int i = 2; i <= max; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * all[i]);
}
return dp[max];
}
}
根据题意，当选择 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] 该如何计算：
1
2
3
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]
时间复杂度：遍历 numsnums 进行计数和取最大值 maxmax，复杂度为 O(n)O(n)；共有 max * 2max∗2 个状态需要被转移，每个状态转移的复杂度为 O(1)O(1)。整体复杂度为 O(n + max)O(n+max)。
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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]);
}
}