LeetCode_动态规划_中等_740.删除并获得点数

1.题目

给你一个整数数组 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 <= nums.length <= 2 * 10⁴
1 <= nums[i] <= 10⁴

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-and-earn

2.思路

（1）动态规划
思路参考本题官方题解。

① 由题意可知，每次操作选择任意一个 x 后，需要删除数组 nums 中所有等于x - 1 和 x + 1 的元素，所以如果选择了 x，为了尽可能地获得点数，我们还应该选择其余等于 x 的元素（此时没有 x - 1 和 x + 1 可被删除，相当于在不删除其它元素的情况下获得点数）。

② 设 maxNum 表示数组 nums 中的最大值，那么可以定义数组 sum，sum[i] 表示数组 nums 中所有元素值为 i 的和。

int[] sum = new int[maxNum + 1];
1

③ 此时，如果选择了 x，那么就可以直接获得 sum[x] 的点数，并且同时不能再选择 x - 1 和 x + 1，即不能获取 sum[x - 1] 和 sum[x + 1] 的点数，此时要求解的问题就与198.打家劫舍这题一模一样了。具体细节可以去看这篇文章，此处不再赘述。

3.代码实现（Java）

//思路1————动态规划
class Solution {
    public int deleteAndEarn(int[] nums) {
        // maxNum 表示数组 nums 中的最大值，初始值为 0
        int maxNum = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }
        // sum[i] 表示数组 nums 中所有元素值为 i 的和
        int[] sum = new int[maxNum + 1];
        for (int num : nums) {
            sum[num] += num;
        }
        return rob(sum);
    }
    
    //下面的代码参考【LeetCode_动态规划_中等_198.打家劫舍】
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int dp0 = nums[0];
        int dp1 = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int tmp = dp1;
            dp1 = Math.max(dp0 + nums[i], dp1);
            dp0 = tmp;
        }
        return dp1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32