简单多状态dp问题----删除并获得点数

740. 删除并获得点数 - 力扣（LeetCode）

本题就是表示不能选值相邻的两个数。 

假设nums = [ 1,2,3,4,5,6]，那么这其实就类似一个打家劫舍问题：

即选1，就不能选2，只能选3，4，5，6。

选2，就不能选1，3，只能选4，5，6。

那么显然：如果选1，最大结果为：1 + 3 + 5

如果选2，最大结果为2 + 4 + 6

但是实际的nums肯定不是一堆连续的数

如：nums = [ 1,1,3,4,4,5,8,8,8]

那么此时我们需要将这个nums数组作预处理：

创建一个arr数组，用来统计每个数出现的总和。

如arr[9]，arr[0] 表示：0出现的总和 = 0。

arr[1]表示1出现的总和 = 2，同理arr[8] = 24。

则此时arr：

val：0  2  0  3  8  5  0  0  24

arr：0  1  2  3  4  5  6  7  8

那么此时，本题就转换为对arr数组作打家劫舍问题了。

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10001;
        int arr[N] = {0};
        for(auto x :nums) arr[x] += x;

        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]);
    }
};