一、题目

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 个点数。

2、基础框架

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {

    }
};

3、原题链接

740. 删除并获得点数

二、解题报告

1、思路分析

  （1）因为题目中整数范围 $\le 10000$，所以可以把每个数字映射到数组中。

当某个数字取了以后，相邻的数字就不可以取：

这不就是打家劫舍 这道题吗？

2、时间复杂度

$O(n)$

3、代码详解

class Solution {
public:
    int rob(vector<int>& nums) {
        int dp[10010];
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (i == 1) { //以防下标溢出，下标为1的情况单独处理
                dp[1] = max(nums[0], nums[1]);
            } else {
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
            }
        }
        return dp[nums.size() - 1];
    }

    int deleteAndEarn(vector<int>& nums) {
        vector<int> sum(10010, 0);
        vector<int> val(10010, 0);
        for (int i = 0; i < nums.size(); ++i) { //所有数字映射到sum数组中
            //sum[i]表示i在数组中的个数
            ++sum[nums[i]];
        }
        for (int i = 0; i <= 10000; ++i) {
            //val[i]代表选取i这个数以后能够获得的点数，就是它本身的值乘上它的个数，即i * sum[i]
            val[i] = i * sum[i];
        }
        return rob(val);
    }
};

或者将 值映射到数组中：

class Solution {
    int rob(vector<int> &sum) {
        int first = sum[0], second = max(sum[0], sum[1]);
        //选择了i，就不能选择相邻的
        for (int i = 2; i < sum.size(); i++) {
            int cur = max(first + sum[i], second);
            first = second;
            second = cur;
        }
        return second;
    }
public:
    int deleteAndEarn(vector<int>& nums) {
        int maxVal = 0;
        //找到数组中的最大值
        for (int val : nums) {
            maxVal = max(val, maxVal);
        }
        //统计每个值的和，如果选了x，则所有的x都会被选到
        vector<int> sum(maxVal + 1, 0); 
        for (int val : nums) {
            sum[val] += val; //sum[i]表示数组中所有i这个数的和，也就是选取i后能获得的点数
        }
        
        return rob(sum);
    }
};

4、复盘

经验：看到数字范围小于 $10^6$，基本就要想一下能否映射到数组下标，从而把问题转换成学过的问题。