小旭讲解 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/