动态规划——删除并获得点数(Leetcode 740)

题目选自Leetcode 740. 删除并获得点数

这道题和打家劫舍其实很类似,只不过因为这道题给的原始数组其实对于元素的值和位置来说并不是连续的,所以我们可以将其转化为统计出每个数字的值,然后进行“打家劫舍”~

 

题目描述:

动态规划——删除并获得点数(Leetcode 740)

动态规划——删除并获得点数(Leetcode 740) 

 

解题思路:

我们可以用类似 桶排序的一个思想, 将每个值的数量统计出来,然后就可以开始DP了 

动态规划——删除并获得点数(Leetcode 740)

动态规划——删除并获得点数(Leetcode 740)

 

思路详解:

首先,我们先明确一个概念,就是每个位置上的数字是可以在两种前结果之上进行选择的:

Case 1:如果你不删除当前位置的数字,那么你得到就是前一个数字的位置的最优结果


Case 2:如果你觉得当前的位置数字i需要被删,那么你就会得到i - 2位置的那个最优结果加上当前位置的数字乘以个数


以上两个结果,你每次取最大的,记录下来,然后答案就是最后那个数字了。

如果你看到现在有点迷糊,那么我们先把数字进行整理一下。

我们在原来的 nums 的基础上构造一个临时的数组 all,这个数组,以元素的值来做下标,下标对应的元素是原来的元素的个数。

动态规划——删除并获得点数(Leetcode 740)

解题代码: 

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];
    }
};

上一篇:acwing 849 Dijkstra求最短路


下一篇:组合数