740. 删除并获得点数

发表于 分类于 阅读次数： Waline： 本文字数： 902 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

1. 问题描述（抽象表述）

给定一个整数数组 nums。 每次可以选择一个数值 x，获得 x 分，并且数组中所有等于 x-1 和 x+1 的元素都会被删除（无法再选择）。

目标是：通过合理选择数值，使得获得的总分最大。

2. 问题建模

2.1 从“元素选择”到“数值选择”

注意到一个关键事实：

  • 如果选择了某个数值 x，那么数组中所有等于 x 的元素都会一起被取走

  • 获得的分数等于 \[ x \times (\text{x 在 nums 中出现的次数}) \]

因此，问题可以等价转化为：

对于每个不同的数值 x，其“价值”为 \[ w(x) = x \cdot \text{count}(x) \] 在数轴上选择若干个数值，使得不选择相邻的数值（x 与 x±1 不能同时选），并使总价值最大。

2.2 与经典问题的对应关系

上述建模与经典的 House Robber（打家劫舍） 问题完全一致：

Delete and Earn House Robber
数值 x 第 i 间房子
w(x) 房子的金钱
不能选 x±1 不能抢相邻房子

区别仅在于：

  • “房子”不是连续编号的，需要先排序、去重。

3. 编程设计

3.1 预处理步骤

  1. 统计权值

    1
    mp[x] += x;

    将相同数值的贡献累加，得到每个数值的总收益。

  2. 排序 + 去重

    1
    2
    sort(nums.begin(), nums.end());
    n = unique(nums.begin(), nums.end()) - nums.begin();

    得到严格递增的数值序列，用于后续 DP。

3.2 状态定义

设去重后的数组为： \[ a_1, a_2, \dots, a_n \] 定义状态： \[ f[i] = \text{只考虑前 } i \text{ 个不同数值时的最大收益} \]

3.3 初始化

  • 空集合： \[ f[0] = 0 \]

  • 只考虑第一个数值： \[ f[1] = w(a_1) \]

4. 状态转移方程

对第 i 个数值（i ≥ 2），记：

  • 当前数值： \[ x = a_i \]

  • 当前收益： \[ y = w(x) \]

分两种情况讨论：

情况 1：数值不相邻

\[ a_i - a_{i-1} > 1 \]

说明当前数值与前一个数值互不冲突，可以直接叠加收益： \[ f[i] = \max\left( f[i-1],\; f[i-1] + y \right) \]

情况 2：数值相邻

\[ a_i - a_{i-1} = 1 \]

不能同时选择，需要在“选”和“不选”之间权衡： \[ f[i] = \max\left( f[i-1],\; f[i-2] + y \right) \]

统一转移逻辑

1
2
3
4
5
f[i] = f[i - 1];
if (a[i] - a[i - 1] > 1)
    f[i] = max(f[i], f[i - 1] + w(a[i]));
else
    f[i] = max(f[i], f[i - 2] + w(a[i]));

5. 时间与空间复杂度分析

  • 排序复杂度： \[ O(n \log n) \]

  • 动态规划： \[ O(n) \]

  • 总时间复杂度： \[ O(n \log n) \]

  • 空间复杂度： \[ O(n) \]

6. 完整 AC 代码（含详细注释）

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    // 最大可能的不同数值数量（题目约束内安全）
    static const int maxn = 2e4 + 5;

    int deleteAndEarn(vector<int>& nums) {
        // mp[x] 表示数值 x 的总收益：x * 出现次数
        unordered_map<int, int> mp;
        for (int x : nums)
            mp[x] += x;

        // 排序以便进行相邻性判断
        sort(nums.begin(), nums.end());

        // 去重，n 为不同数值的个数
        int n = unique(nums.begin(), nums.end()) - nums.begin();

        // f[i]：只考虑前 i 个不同数值时的最大收益
        int f[maxn];

        // 初始化
        f[0] = 0;
        f[1] = mp[nums[0]];

        // 动态规划转移
        for (int i = 2, x, y; i <= n; ++i) {
            // 当前数值
            x = nums[i - 1];
            // 当前数值的总收益
            y = mp[x];

            // 情况：不选当前数值
            f[i] = f[i - 1];

            // 判断是否与前一个数值相邻
            if (x - nums[i - 2] > 1)
                // 不相邻：可以直接叠加
                f[i] = max(f[i], f[i - 1] + y);
            else
                // 相邻：只能从 f[i-2] 转移
                f[i] = max(f[i], f[i - 2] + y);
        }

        // 返回最终答案
        return f[n];
    }
};