小旭讲解 LeetCode 740. Delete and Earn
小旭讲解 LeetCode 740. Delete and Earn

题目

LeetCode 740. 删除与获得点数

思路

本质上该题是线性 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/
0 0 vote
Article Rating
Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments

[…] 小旭讲解 LeetCode 740. 删除与获得点数 […]