力扣LeetCode: 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 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= 10^4

解法：动态规划

这个问题可以通过动态规划来解决。我们可以将问题转化为一个类似于“打家劫舍”的问题，即不能选择相邻的元素。具体来说，我们可以通过以下步骤来解决这个问题：

问题分析

1. 选择元素：每次选择一个元素 nums[i]，获得 nums[i] 的点数。

2. 删除相邻元素：删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

3. 目标：最大化获得的点数。

解决思路

1. 统计每个数字的出现次数：我们可以用一个哈希表（或数组）来统计每个数字的出现次数，并计算每个数字的总点数（即数字乘以它的出现次数）。

2. 转化为动态规划问题：类似于“打家劫舍”问题，我们不能选择相邻的数字。因此，我们可以使用动态规划来计算最大点数。

3. 状态转移方程：

   • 如果选择当前数字 i，则不能选择 i-1，所以最大点数为 dp[i-2] + points[i]。

   • 如果不选择当前数字 i，则最大点数为 dp[i-1]。

   • 因此，状态转移方程为：

                                 dp[i]=max⁡(dp[i−1],dp[i−2]+points[i]）

代码实现

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if (nums.empty()) return 0;

        // 找到数组中的最大值
        int maxNum = *max_element(nums.begin(), nums.end());

        // 统计每个数字的总点数
        vector<int> points(maxNum + 1, 0);
        for (int num : nums) {
            points[num] += num;
        }

        // 动态规划数组
        vector<int> dp(maxNum + 1, 0);
        dp[0] = 0; // 没有数字时点数为 0
        dp[1] = points[1]; // 只有一个数字时点数为 points[1]

        // 填充 dp 数组
        for (int i = 2; i <= maxNum; ++i) {
            dp[i] = max(dp[i-1], dp[i-2] + points[i]);
        }

        // 返回最大点数
        return dp[maxNum];
    }
};

代码解释

1. 统计每个数字的总点数：

   • 使用 points 数组来存储每个数字的总点数。例如，如果数字 3 出现了 2 次，则 points[3] = 3 * 2 = 6。

2. 动态规划数组 dp：

   • dp[i] 表示从 0 到 i 的数字中可以获得的最大点数。

   • 初始化 dp[0] = 0（没有数字时点数为 0）和 dp[1] = points[1]（只有一个数字时点数为 points[1]）。

3. 状态转移：

   • 对于每个数字 i，我们有两种选择：

     • 不选择 i，则最大点数为 dp[i-1]。

     • 选择 i，则最大点数为 dp[i-2] + points[i]。

   • 我们取这两种选择中的最大值作为 dp[i]。

4. 返回结果：

   • 最终 dp[maxNum] 就是可以获得的最大点数。

示例

假设输入数组为 [3, 4, 2]，执行过程如下：

1. 统计每个数字的总点数：

   • points = [0, 0, 2, 3, 4]（因为数字 2 出现 1 次，3 出现 1 次，4 出现 1 次）。

2. 动态规划：

   • dp[0] = 0。

   • dp[1] = 0。

   • dp[2] = max(dp[1], dp[0] + 2) = max(0, 2) = 2。

   • dp[3] = max(dp[2], dp[1] + 3) = max(2, 3) = 3。

   • dp[4] = max(dp[3], dp[2] + 4) = max(3, 6) = 6。

3. 返回结果 6。

时间复杂度

• 时间复杂度为 O(n + k)，其中 n 是数组 nums 的长度，k 是数组中的最大值。

  • 统计每个数字的总点数需要 O(n)。

  • 动态规划需要 O(k)。

空间复杂度

• 空间复杂度为 O(k)，用于存储 points 和 dp 数组。

总结

通过将问题转化为动态规划问题，我们可以高效地解决这个问题。关键在于统计每个数字的总点数，并使用状态转移方程来计算最大点数。