2021/4/19 删除与获得点数

题目描述

描述转载自力扣《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];
    }
}