参考链接
https://leetcode-cn.com/problems/delete-and-earn/
题目描述
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
解题思路
本题需要明确的一点是，如果删除了有多个相同值的元素，因为比它大1或小1的元素都被删了，后面这些相同的元素还会被剩下，所以可以一次全部删除。
回溯法
即暴力穷举所有情况。首先用哈希表记录所有相同元素的和，穷举哈希表的每一个键，记录下它的值，并去除哈希表中键比它大1和小1的值，递归后再恢复。（会超时！）
递归式动态规划
先对数组进行排序，然后用哈希表记录所有相同元素的和，同时新建一个记录所有不重复元素的数组，这样就可以把“状态”设为不重复数组的索引了，状态表存储的就是当前索引到最后一个索引间能获得的最大点数。“选择”就是是否删除当前索引处元素。如果要删除当前元素，这一步中需要判断下一个元素与当前元素的差是否等于1，如果等于1，就往下跳2个元素，否则跳1个元素；如果不删除当前元素，则直接跳一个元素。
迭代式动态规划
官方解法用数组代替哈希表存储相同元素的元素和，这样每个元素间的差都是1，状态表记录第0个元素到当前元素能获得的最大点数。“选择”是是否删除当前元素，如果删除，点数为当前元素与第0个元素到前2个元素的最大点数和，如果不删，就是第0个元素到前一个元素的最大点数。
排序 + 动态规划
同样是官方的最优解法，若 nums 中不存在某个元素 x，则选择任一小于 x 的元素不会影响到大于 x 的元素的选择。因此我们可以将 nums 排序后，将其划分成若干连续子数组，子数组内任意相邻元素之差不超过 1。对每个子数组按照方法一的动态规划过程计算出结果，累加所有结果即为答案。
代码
回溯法
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
unordered_map<int, int> mp;
for (int num : nums)
{
mp[num] += num;
}
int res = Earn(mp);
return res;
}
int Earn(unordered_map<int, int>& mp)
{
int res = 0;
for (auto& item : mp)
{
if (mp[item.first] == 0)
{
continue;
}
int sum = mp[item.first];
mp[item.first] = 0;
int prev_plus_1 = mp[item.first + 1];
int prev_sub_1 = mp[item.first - 1];
mp[item.first + 1] = 0;
mp[item.first - 1] = 0;
res = max(res, sum + Earn(mp));
mp[item.first] = sum;
mp[item.first + 1] = prev_plus_1;
mp[item.first - 1] = prev_sub_1;
}
return res;
}
};
递归式动态规划
class Solution {
public:
unordered_map<int, int> memo;
int deleteAndEarn(vector<int>& nums) {
sort(nums.begin(), nums.end());
unordered_map<int, int> mp;
vector<int> unique;
int tmp = INT_MAX;
for (int num : nums)
{
if (tmp != num)
{
unique.push_back(num);
tmp = num;
}
mp[num] += num;
}
unique.push_back(INT_MAX);
int res = dp(mp, unique, 0);
return res;
}
int dp(unordered_map<int, int>& mp, vector<int>& nums, int start)
{
if (start + 1 >= nums.size())
{
return 0;
}
if (memo.count(start) == 1)
{
return memo[start];
}
int do_it = 0;
if (nums[start] - nums[start + 1] == 1 || nums[start + 1] - nums[start] == 1)
{
do_it = mp[nums[start]] + dp(mp, nums, start + 2);
}
else
{
do_it = mp[nums[start]] + dp(mp, nums, start + 1);
}
int not_do = dp(mp, nums, start + 1);
memo[start] = max(do_it, not_do);
return max(do_it, not_do);
}
};
迭代式动态规划
class Solution {
private:
int rob(vector<int> &nums) {
int size = nums.size();
int first = nums[0], second = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}
public:
int deleteAndEarn(vector<int> &nums) {
int maxVal = 0;
for (int val : nums) {
maxVal = max(maxVal, val);
}
vector<int> sum(maxVal + 1);
for (int val : nums) {
sum[val] += val;
}
return rob(sum);
}
};
排序 + 动态规划
class Solution {
private:
int rob(vector<int> &nums) {
int size = nums.size();
if (size == 1) {
return nums[0];
}
int first = nums[0], second = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}
public:
int deleteAndEarn(vector<int> &nums) {
int n = nums.size();
int ans = 0;
sort(nums.begin(), nums.end());
vector<int> sum = {nums[0]};
for (int i = 1; i < n; ++i) {
int val = nums[i];
if (val == nums[i - 1]) {
sum.back() += val;
} else if (val == nums[i - 1] + 1) {
sum.push_back(val);
} else {
ans += rob(sum);
sum = {val};
}
}
ans += rob(sum);
return ans;
}
};
