[数据结构与算法]LeetCode动态规划 删除并获得点数

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.
Return the maximum number of points you can earn by applying the above operation some number of times.

这道题是我做动态规划碰到的第一个下马威，没有识别出这是一道动态规划题。实际上，这题跟“打家劫舍”那道题的核心思想是一模一样的。重点是如何理解获得一个数后，就要删除和它相邻的数。其实，可以将这句话转述成：不能取两个相邻的数。这样就很容易地解决了本题。

状态转移方程
dp[i] = max(dp[i-2] + dp[i], dp[i-1])
边界条件
dp[0] = dp[0], dp[1] = max(dp[0], dp[1])

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int nums_top = nums.size();
        if(nums_top == 0)
        return 0;
        else if(nums_top == 1)
        return nums[0];

        int dp[20005] = {0};
        int maxn = -1;
        for(int i = 0; i < nums_top; i++)
        {
            dp[nums[i]] += nums[i];
            if(nums[i] > maxn)
            maxn = nums[i];
        }
        dp[1] = max(dp[0], dp[1]);
        for(int i = 2; i <= maxn; i++)
        dp[i] = max(dp[i-2]+dp[i], dp[i-1]);
        
        return dp[maxn];
    }
};