力扣AC：删除并获得点数 - 动态规划

题目链接

删除并获得点数

题目描述

实现代码

思路：由题意得知，如果选择元素值x，那么元素值x相邻的两个整数x-1 和 x+1都不能被选取，同时将所有的x选取并删除；因此，我们可以先将数组进行排序，然后将重复元素进行移除并累加，最终得到缩减版的无重复元素的排序数组，然后问题就演变成了打家劫舍；

实现代码如下（这里未使用排序 + dp，直接使用的dp）：

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }
    public int rob(int[] nums) {
        int size = nums.length;
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}