力扣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^41 <= nums[i] <= 10^4 解法：动态规划

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

问题分析

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

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

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

解决思路

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

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

状态转移方程：

如果选择当前数字 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]; } }; 代码解释

统计每个数字的总点数：

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

动态规划数组 dp：

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

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

状态转移：

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

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

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

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

返回结果：

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

示例

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

统计每个数字的总点数：

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

动态规划：

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。

返回结果 6。

时间复杂度

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

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

动态规划需要 O(k)。

空间复杂度

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

总结

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