题解

用count数组记录每个数字出现的次数
因为选择任意一个数字x记录其点数都是记录n个x
同时删除也是删除若干个x-1或者x+1
DP思路和大盗阿福其实一样的

代码

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int N=2e4+10,n=1e4+10;
        int f[N][2],count[N];
        memset(f,0,sizeof f);
        memset(count,0,sizeof count);
        for(auto x:nums){
            count[x]++;
        }
        for(int i=1;i<=n;i++){
            f[i][0]=max(f[i-1][1],f[i-1][0]);
            f[i][1]=f[i-1][0]+count[i]*i;
        }
        return f[n][0];
    }
};