Delete and Earn

给一个数组, 给一个操作: 删除一个数字, 然后得到这个数字的分数, 并且必须删除这个数字-1和+1的所有数字, 求最大的分数.

这题就是dp+贪心, 因为要得到最高的分数, 所以肯定要删大的先, 找到最大的删后, 就不用担心这个数字有+1的数字被删掉了. 然而只是贪心不够的, 因为如果是按照排序的数删除的话, 会有[10,8,8,8,8,8]这类情况, 所以还是要dp.

那么设dp[i]为删到大小为i的时候最大的分数. 那么dp[0] = 0, dp[1] = {all 1}, dp[2] = max{all 2 + dp[0], dp[1]}. dp[3] = max{all 3 + dp[1], dp[2]}

dp[i] = {dp[i-2] + sum[i], dp[i-1]}意义是: 两种选法儿, 第一种是选i-2的最佳答案,并且加上sum[i], 因为隔了一个, 所以是能选的. 第二种选法是选上一个的最佳答案, 这次的不要了

class Solution {
    int N = 100001;
    public int deleteAndEarn(int[] nums) {
        int[] sum = new int[N];
        int[] dp = new int[N];
        for(int n : nums)
            sum[n] += n;
        dp[0] = 0;
        dp[1] = sum[1];
        for(int i = 2; i < N; i++)
        {
            dp[i] = Math.max(dp[i - 2] + sum[i], dp[i - 1]);
        }
        //dp[0] = 0
        //dp[1] = sum[1]; all 1's score, because 0 has 0 score.
        //dp[2] = max(dp[0] + sum[2],dp[1])
        return dp[N - 1];
    }
}