【算法】动态规划 斐波那契类型： 740. 删除并获得点数

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 * 104
1 <= nums[i] <= 104

分析

这是一个非常经典的动态规划问题，跟「打家劫舍」非常相似。

问题本质：

• 如果你选了一个数 x，你会获得 x * 出现次数 的分数，并且不能再选 x-1 和 x+1。
• 所以你不能同时选相邻的数（按照值排序）。
• 相当于：把所有数按照值排序，把它们看成一排房子（每个房子有一定价值），不能取相邻的房子。

下面一步一步讲解和给出代码。

🟢 思路步骤

1. 统计每个数字的总价值：

   • 用一个数组 sum[x] = x * 出现次数。

   • 例如 nums = [2,2,3,3,3,4]：

     • 2出现2次，贡献=2*2=4
     • 3出现3次，贡献=3*3=9
     • 4出现1次，贡献=4*1=4

2. 动态规划：

   • 定义 dp[i]：考虑数字0~i，能取得的最大分数。

   • 转移方程：

     dp[i] = max(
         dp[i-1],            // 不取i
         dp[i-2] + sum[i]    // 取i
     )
     

   • 为什么和打家劫舍一样？因为选了i就不能选i-1。

3. 初始化：

   • dp[0] = sum[0]
   • dp[1] = max(sum[0], sum[1])

4. 返回：

   • dp[max_value]，max_value = max(nums)

🟢 Python代码

def deleteAndEarn(nums):
    if not nums:
        return 0

    max_num = max(nums)
    sum_points = [0] * (max_num + 1)

    # 统计每个数的总价值
    for num in nums:
        sum_points[num] += num

    # 动态规划
    dp = [0] * (max_num + 1)
    dp[0] = sum_points[0]
    dp[1] = max(sum_points[0], sum_points[1])

    for i in range(2, max_num + 1):
        dp[i] = max(dp[i - 1], dp[i - 2] + sum_points[i])

    return dp[max_num]

🟢 示例验证

示例1:

nums = [3,4,2]
sum_points: [0,0,2,3,4]
dp:
i=2: dp[2]=max(dp[1], dp[0]+sum[2]) = max(0,0+2)=2
i=3: dp[3]=max(dp[2], dp[1]+sum[3]) = max(2,0+3)=3
i=4: dp[4]=max(dp[3], dp[2]+sum[4]) = max(3,2+4)=6
输出:6

示例2:

nums = [2,2,3,3,3,4]
sum_points: [0,0,4,9,4]
dp:
i=2: dp[2]=max(dp[1], dp[0]+sum[2]) = max(0,0+4)=4
i=3: dp[3]=max(dp[2], dp[1]+sum[3]) = max(4,0+9)=9
i=4: dp[4]=max(dp[3], dp[2]+sum[4]) = max(9,4+4)=9
输出:9

✅完全符合题意。

c++

🟢 C++代码

#include <vector>
#include <algorithm>
using namespace std;

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

        int maxNum = *max_element(nums.begin(), nums.end());

        // sum[i] = i * 出现次数
        vector<int> sum(maxNum + 1, 0);
        for (int num : nums) {
            sum[num] += num;
        }

        // dp[i] = 考虑[0..i]的最大点数
        vector<int> dp(maxNum + 1, 0);
        dp[0] = sum[0];
        dp[1] = max(sum[0], sum[1]);

        for (int i = 2; i <= maxNum; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + sum[i]);
        }

        return dp[maxNum];
    }
};

🟢 用法示例

你可以这样调用：

#include <iostream>

int main() {
    Solution s;
    vector<int> nums = {2,2,3,3,3,4};
    cout << s.deleteAndEarn(nums) << endl;  // 输出 9
    return 0;
}

**空间优化（O(1)空间）**

非常好问题！

这个DP转移：

$$dp[i]=\max (dp[i-1],dp[i-2]+sum[i])$$

只用到了 i-1 和 i-2，所以不需要存整个数组，只需要两个变量即可。

🟢 O(1)空间优化思路

• 维护两个变量：

  • prev1：表示 dp[i-1]
  • prev2：表示 dp[i-2]

• 每次更新：

  curr = max(prev1, prev2 + sum[i]);
  

  然后：

  prev2 = prev1;
  prev1 = curr;
  

🟢 完整C++代码（O(1)空间）

#include <vector>
#include <algorithm>
using namespace std;

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

        int maxNum = *max_element(nums.begin(), nums.end());

        vector<int> sum(maxNum + 1, 0);
        for (int num : nums) {
            sum[num] += num;
        }

        int prev2 = sum[0];                        // dp[i-2]
        int prev1 = max(sum[0], sum[1]);           // dp[i-1]
        int curr = prev1;

        for (int i = 2; i <= maxNum; ++i) {
            curr = max(prev1, prev2 + sum[i]);
            prev2 = prev1;
            prev1 = curr;
        }

        return curr;
    }
};

🟢 样例验证

如示例：

int main() {
    Solution s;
    vector<int> nums = {2,2,3,3,3,4};
    cout << s.deleteAndEarn(nums) << endl;  // 输出 9
    return 0;
}

✅ 输出正确。

这样就只用 O(1) 空间，时间复杂度依然是 O(N)。

如需要，我也可以帮你写 Java版本 或进一步优化逻辑！