题目
思路
本质上该题是线性 DP,仔细研究可以发现,题目中给了计算点数的策略,是和当前选择元素的点数 nums[i] 有关,即获得了 nums[i] 个点数,失去了所有点数等于 nums[i] – 1 和 nums[i] + 1 的点数,则不妨将问题的状态区间转换为 [1, max(nums[i)] 上来,其代表可选择的值(点数 / nums[i])的范围。
如果用线性状态空间描述问题 f[j],代表 [0,j] 闭区间能够获得的最大点数,那么 f[j] 可以由其更小的线性状态空间递推计算出来。
如果选择值(点数 / num[i])为 j 的元素,那么 f[j] = f[j-2] + cnt[j] * j;如果不选择值为 j 的元素,那么 f[j] = f[j-1]。
cnt[j] 代表在 nums 中值为 j 的个数。
代码
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
vector<int> cnt(10010, 0), f(10010, 0);
for(auto n:nums) cnt[n]++;
f[1] = cnt[1];
int ans=0;
for (int i=2;i<=10000;++i) {
f[i] = max(f[i-2] + i * cnt[i], f[i-1]);
ans=max(f[i],ans);
}
return ans;
}
};
复杂度
Time:O(N) N = max(nums.length, max(nums[i]))
Space: O(M) M = max(nums[i])
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-740-delete-and-earn/
[…] 小旭讲解 LeetCode 740. 删除与获得点数 […]