一、题目

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

点击查看原题

二、思路

本题思路与打家劫舍的思路基本一致。只是题目表述不清晰。
由于选择了nums[i]后只能获取nums[i]的点数，而nums[i] - 1 或 nums[i] + 1 都不能获取，可以化简为子问题，即用一个数组sum，sum[i]是nums数组中有n个i的值。那么只需要考虑选择了sum[i]就不可以选择sum[i-1]即可，可以得到状态转移方程为：

由于只依赖于前两项，可以压缩动态规划数组为两个变量，即first为dp[i-2]，second为dp[i-1]。

三、代码

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxValue = 0;
        for (int num : nums) {    //找到数组中最大值
            maxValue = Math.max(maxValue, num);
        }
        int[] sum = new int[maxValue + 1];
        for (int num : nums) {    // sum[i]为nums中所有i之和
            sum[num] += num;
        }
        // 动态规划求解
        int first = sum[0], second = Math.max(sum[0], sum[1]);
        for (int i = 2; i < sum.length; i++) {
            int t= second;
            second = Math.max(second, sum[i] + first);
            first = t;
        }
        return second;
    }
}