给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2] 输出：6 解释： 删除 4 获得 4 个点数，因此 3 也被删除。 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4] 输出：9 解释： 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。 总共获得 9 个点数。
提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104
解题分析
这道题设计的比较巧妙，可以利用动态规划的思路来解决问题。我们先理解一下题目的意思，然后尝试将它转换为一个经典的动态规划模型。我们知道，如果我们选择了nums[i]，那么我们就不能选择nums[i]-1和nums[i]+1，而题目要求我们获得最大点数，所以我们也应当选择所有的与nums[i]相等的那些数，也就是说假如与nums[i]相等的数有x个，那么我们就可以得到x * nums[i]个点数。接下来就有意思了，不妨创建一个数组sum，这个sum数组的特点是sum[nums[i]] = nums[i] * x。其中x为个数。这样我们创建一个dp数组，dp[i]表示到第i个位置的时候，我们隔位选座（也就是说我们如果选了sum[c]，那么我们就不能选它相邻位置的sum[c-1] 和 sum[c+1]) 能够得到的最大点数。显然，我们有递推关系式 dp[i] = max(dp[i-1],dp[i-2]+sum[i])。也就是说，如果我们选择第i个位置，那我们可以得到第i个位置的点数sum[i] 加上 我们到第i-2个位置时选座的最大点数。如果我们不选择第i个位置，那我们就可以考虑选第i-1个位置，而我们又确定了不选第i个位置，所以得到dp[i]就直接等于dp[i-1]即可。最后输出dp[n-1]即可。
代码实现
class Solution {
private:int rob(vector<int> &nums){int n = nums.size();vector<long long> dp(n);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<n;i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}return dp[n-1];}
public:int deleteAndEarn(vector<int>& nums) {int maxVal = 0;for(int val : nums){maxVal = max(maxVal,val);}vector<int> sum(maxVal+1);for(int val:nums){sum[val] += val;}return rob(sum);}
};
