「动态规划」删除并获得点数

力扣原题链接，点击跳转。

给你一个整数数组nums。每次操作，可以删除任意一个值n，接着获得点数n，并同时删除所有的n-1和n+1。你最多能获取多少点数？

这个问题的解法相当巧妙。我们可以把问题先转化一下。用类似计数排序的思路，定义一个数组arr，用arr[i]表示所有的点数i的和。比如nums数组：1、2、2、3、3、3，那么arr数组：0、1、4、9，因为1出现1次，和为1；2出现2次，和为2×2=4；3出现3次，和为3×3=9。

盯着这个arr数组，问题就转化为：在arr数组中选取一个子数组，不能同时选取相邻的元素，请找出一个子数组，让这个子数组所有元素的和最大。如果你看到这里，觉得这道题跟某一道经典问题很像，有这种感觉就对了。具体请看我的另一篇博客：「动态规划」打家劫舍，点击跳转。有了打家劫舍的铺垫，这个问题就非常简单了，思路可以说是一模一样。

用动态规划的思路来解决这个问题。首先确定状态表示，用f[i]表示选到下标为i的元素时，必须选择下标为i的元素，子数组的最大和；用g[i]表示选到下标为i的元素时，不能选择下标为i的元素，子数组的最大和。接着推导状态转移方程，显然f[i]=g[i-1]+arr[i]，g[i]=max(f[i-1],g[i-1])。初始化f[0]=arr[0]=0，g[0]=0。为什么arr[0]=0呢？因为点数0不管选多少，和都是0。填表时应从左往右同时填表。arr有n个元素，最后返回max(f[n-1],g[n-1])。

class Solution
{
public:int deleteAndEarn(vector<int>& nums){const int N = 10001;// 用arr[i]表示所有点数i的和vector<int> arr(N);for (auto num : nums)arr[num] += num;// 创建dp表vector<int> f(N);auto g = f;// 填表for (int i = 1; i < N; i++){f[i] = g[i - 1] + arr[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[N - 1], g[N - 1]);}
};