这道题和打家劫舍其实很类似,只不过因为这道题给的原始数组其实对于元素的值和位置来说并不是连续的,所以我们可以将其转化为统计出每个数字的值,然后进行“打家劫舍”~
题目描述:
解题思路:
我们可以用类似 桶排序的一个思想, 将每个值的数量统计出来,然后就可以开始DP了
思路详解:
首先,我们先明确一个概念,就是每个位置上的数字是可以在两种前结果之上进行选择的:
Case 1:如果你不删除当前位置的数字,那么你得到就是前一个数字的位置的最优结果。
Case 2:如果你觉得当前的位置数字i需要被删,那么你就会得到i - 2位置的那个最优结果加上当前位置的数字乘以个数。
以上两个结果,你每次取最大的,记录下来,然后答案就是最后那个数字了。如果你看到现在有点迷糊,那么我们先把数字进行整理一下。
我们在原来的 nums 的基础上构造一个临时的数组
all
,这个数组,以元素的值来做下标,下标对应的元素是原来的元素的个数。
解题代码:
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
if(nums.size() < 1) return 0;
int maxn = 0;
for(int it : nums)
maxn = max(maxn, it);
vector<int> cnt(maxn+1), dp(maxn+1);
for(int it : nums)
cnt[it]++;
dp[1] = cnt[1];
for(int i = 2; i <= maxn; i++)
dp[i] = max(dp[i-1], dp[i-2] + cnt[i] * i);
return dp[maxn];
}
};