题目描述：给你一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

方法1：动态规划，如果上一次选择的点数和这一次一样（这一次也直接取），如果上一次选择的点数比这一次只小1（取上一次与上t次的最大值，上t次刚好和上一次不一样），不仅仅只小1（也直接取）

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int>dp(nums.size()+1); //前i个数能获得的最大点数
        sort(nums.begin(),nums.end());
        dp[0] = 0;
        dp[1] = nums[0];
        int t=1;

        for(int i=1;i<nums.size();i++){
            if(nums[i] == nums[i-1]){
                dp[i+1] = dp[i] + nums[i];
                t++;
            }
            else if(nums[i] == nums[i-1] +1){
                dp[i+1] = max(dp[i],dp[i-t]+nums[i]);
                t = 1;
            }
            else dp[i+1] = dp[i] + nums[i];
        }
        return dp[nums.size()];
    }
};

出错，第一个if循环错误，nums[i-1]不一定是上一次选择的点数，如果（2，2，3，3，3）应该是9，以这个逻辑却是10，取了两个2后，第一个3会舍弃，但是第二个3与第三个3会任务上一次选择的是3，从而会直接取

解决办法：用一个哈希表记录每一个数在数组中出现的次数

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        unordered_map<int,int>count;//每个不一样的nums[i]出现的次数
        for(int i=0;i<nums.size();i++){
            count[nums[i]]++;
        }
        
        vector<int>dp(count.size()+1); //前i个数能获得的最大点数
        auto p = count.begin();
        auto q = count.begin();
        dp[0] = 0;
        dp[1] = (p->first) * (p->second);

        for(int i=2;i<count.size()+1;i++){
            q++;
            if(p->first == q->first-1) dp[i] = max(dp[i-1],dp[i-2] + q->first * q->second);
            else dp[i] = dp[i-1] + q->first * q->second;
        }
        return dp[count.size()];
    }
};

出错，哈希表中key的顺序并不是存放的先后顺序，q->first与p->first在排序后的nums[i]中并不一定是靠在一起的

解决办法，用一个数组存放key，再对数组排序

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        unordered_map<int,int>count;//每个不一样的nums[i]出现的次数
        vector<int> single_num;
        for(int i=0;i<nums.size();i++){
            count[nums[i]]++;
        }
        for(auto it = count.begin();it!=count.end();it++) single_num.push_back(it->first);//用一个数组存放key
        sort(single_num.begin(),single_num.end());

        vector<int>dp(single_num.size()+1); 
        dp[0] = 0;
        dp[1] = single_num[0] * count[single_num[0]];

        for(int i=2;i<single_num.size()+1;i++){
            if(single_num[i-1] == single_num[i-2]+1) dp[i] = max(dp[i-1],dp[i-2] + single_num[i-1] * count[single_num[i-1]]);
            else dp[i] = dp[i-1] + single_num[i-1] * count[single_num[i-1]];
        }
        return dp[single_num.size()];
    }
};

方法2：将题目改造成打家劫舍，设max_val是nums数组中最大的数，设有max_val间房子，第val个房子存的钱为（val） * （val出现的次数）

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int max_val = *max_element(nums.begin(),nums.end());
        vector<int> house(max_val+1,0);
        for(int i=0;i<nums.size();i++) house[nums[i]] += nums[i];

        //打家劫舍
        int p=0,q=house[0];int m = q;
        for(int i=1;i<house.size();i++){
            m = max(p+house[i],q);
            p = q;
            q = m;
        }
        return m;
    }
};