Delete and Earn

跟之前的上楼梯问题有点像，其实就是一个数组nums选中了一个数以后，它的连续的前一个或者后一个都要删掉，求可获得的最大的和。
算法过程分析：在到达一个数时，只能选择留下前一个数，或者留下前前一个数加上现在的值，用totol记录某一个数的最大值，那么转移方程为totol[i] = max(totol[i - 1], totol[i - 2] + nums[i])，因为还有很多重复的值，所以用了一个map来记录有多少重复的，并且map已经是排好序的，这一点很方便。
以下是代码：

class Solution {
public:int deleteAndEarn(vector<int>& nums) {if(nums.empty()) return 0;map<int, int> m;vector<int> totol(10010, 0);int res = 0, last, last1;for (int i = 0; i < nums.size(); i++) {auto it = m.find(nums[i]);if(it == m.end()) m[nums[i]] = 1;else m[nums[i]] = m[nums[i]] + 1;}auto it = m.begin();totol[it -> first] = it -> first * it -> second;res = totol[it -> first];last = last1 = it -> first;int i = 1;for (it++; it != m.end(); it++, i++) {if(last1 + 1 == it -> first) {if(i == 1) {totol[it -> first] = max(it -> first * it -> second, totol[last]);last1 = it -> first;} else {totol[it -> first] = max(totol[last1], totol[last] + it -> first * it -> second);last = last1;last1 = it -> first;}} else {totol[it -> first] = totol[last1] + it -> first * it -> second;last = last1;last1 = it -> first;}if(res < totol[it -> first]) res = totol[it -> first];}
        return res;}
};

这一题写的比较复杂，看到了discuss以后，发现一个非常简单的dp方法，我写的复杂是因为在考虑第一个数和第二个该怎么获取，这里变得很麻烦，discuss的方法是将其存到数组中，从第0个开始，dp[i]表示i可以获取最多的数，这里学到了一个，把数放后一个，而不是从头开始放。
下面是discuss的代码：
“`c++
int deleteAndEarn(vector& nums) {
if(nums.size()==0) return 0;

    std::vector<int> a(10001,0); // frequency of numbers from 1 to 10000for(int i:nums){++a[i];}std::vector<int> dp(a.size()+1,0);dp[1]=a[1]*1;for(int i=2;i<=10000;++i){dp[i]=std::max(dp[i-1],a[i]*i+dp[i-2]);}return dp[10000];
}
```