动态规划：删除并获得点数

题目来源：删除并获得点数

题目分析

题目分析：

从题目中可以获取到的条件是，如果选择了i位置，那么就必须删除与i-1和i+1的位置的值相同的所有的值。

既然要删除相同的值，那么我们可以想，要不要先排序，将相同的值都放到一起，好操作！而我们又可以想，既然要删除所有相同的值的元素，那不入干脆求了和，再放入数组中。

那怎么放入呢？既然用到数组了，那么将数组利用好，我们可以使用数组下标来操作，0位置对应0元素，1位置对应1，将所有1全部加起来，再放到1位置上，于此类推！

 于是，我们就可以将问题转化了！转化成类似“打家劫舍”这道题目了！题目讲解：

这里简单说一下，我们把问题转化成了求数组中的最大和，但是，当选择了i位置的元素，那么i-1和i+1位置的元素就不能选择了，需要跳开一个来选择。

状态表示

f[i]表示到达 i 这个位置，选择值为 i 的元素。

g[i]表示，到达 i 这个位置，不选择 i 这个元素。

状态转移方程

f[i] = g[i-1] + nums[i];

g[i-1] = (f[i-1],g[i-1]);

初始化

从状态转移方程中可以知道，我们需要从i =1出发，为了不越界，需要将i==0这个位置初始化。因为f[i]是选择的，那么将f[0] = nums[0]，g[i]不选择，则g[0] = 0；

方向是从左到右开始计算结果。

返回值

在到达最后的位置，有两种选择，一是不选择，二是选择，因此最终结果是在这两种情况下，选择最大值的：

return max(f[n-1],g[n-1]);

编写代码 

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10001;
        int arr[N] = {0};
        for(auto x:nums)/*将i元素，求和到i位置上*/
        {
            arr[x]+=x;
        }
        vector<int> f(N);
        auto g = f;
        f[0] = arr[0];
        for(int i = 1;i<N;++i)
        {
            f[i] = g[i-1]+arr[i];
            g[i] = max(g[i-1],f[i-1]);
        }
        return max(f[N-1],g[N-1]);
    }
};

总结：

拿到题目先不急着写代码，而是先挖掘题目的条件，根据条件来解析题目，用到数组时，想一想能不能利用它的下标的映射关系等等。