题目描述

描述转载自力扣《740. 删除与获得点数》

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

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

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

示例1

输入: nums = [3, 4, 2]
输出: 6
解释:
删除 4 来获得 4 个点数,因此 3 也被删除。
之后,删除 2 来获得 2 个点数。总共获得 6 个点数。

示例2

输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释:
删除 3 来获得 3 个点数,接着要删除两个 2 和 4 。
之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。
总共获得 9 个点数。

解题思路

  1. 这题属于《打家劫舍》 类型的动态规划题,建议先做此题。在打家劫舍中,我们得出状态转移方程 图片说明 ,意思是如果选择了第 i 家,那么选择了第 i 家的最优值就是第 i 家加上选择了第 i - 2 家的最优值;如果不选第 i 家,那么第 i 家的最优值就是选择了第 i - 1 家的最优值。
  2. 此题类似,如果我们选择了 i,那么 i - 1 和 i + 1 都不在考虑范围内,因为被删除了,和打家劫舍的相邻房间不能选是一样的,但如果遇上了 n 个同样的值 i,就需要将结果加上 图片说明 了。所以状态转移方程是 图片说明
  3. 我使用了 Map 存储每个值 i 的个数 n,组成 K-V 映射(i, n),当然也可以使用数组的下标和元素作映射,全看喜好。

Java代码实现

class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums.length == 1) return nums[0];
        Arrays.sort(nums);
        int len = nums.length;
        HashMap<Integer, Integer> numsOfEle = new HashMap<>();
        for (int i = 0; i < len; ++i) {
            int value = 1;
            if (numsOfEle.containsKey(nums[i])) {
                value += numsOfEle.get(nums[i]);
            }
            numsOfEle.put(nums[i], value);
        }

        // dp[i] = max(dp[i-1], dp[i-2] + i * map(i))
        int[] dp = new int[nums[len - 1] + 1];
        if (numsOfEle.containsKey(1)) dp[1] = numsOfEle.get(new Integer(1));
        if (numsOfEle.containsKey(2)) dp[2] = numsOfEle.get(new Integer(2)) * 2;
        dp[2] = Math.max(dp[1], dp[2]);

        for (int i = 3; i < dp.length; ++i) {
            int num = 0;
            if (numsOfEle.containsKey(i)) num = numsOfEle.get(new Integer(i));
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * num);
        }

        return dp[dp.length - 1];
    }
}