删除并获得点数如何转化为打家劫舍？为什么相邻数值不能同时选？

简化版

删除并获得点数可以先把相同数字合并成总收益 sum[x] = x * count[x]。如果选择数字 x，就不能选择 x-1 和 x+1，这和打家劫舍中不能偷相邻房子一样，所以对数值轴做打家劫舍 DP。

详细版

先统计每个数字出现次数，得到每个数值点的总收益。然后按数值从小到大遍历，定义 dp[i] 表示考虑到数值 i 时能获得的最大点数，转移为 dp[i] = max(dp[i-1], dp[i-2] + sum[i])。

如果数值范围很大但元素数量不多，可以先排序去重，用 take/skip 或映射数组处理断开的数值。时间复杂度取决于实现：按最大值数组是 O(maxVal+n)，排序去重是 O(n log n)。

完整版教学

一、题目规则为什么像打家劫舍

删除一个数字 x 后，所有 x-1 和 x+1 都会被删除，所以你不能同时获得相邻数值的收益。注意这里的“相邻”不是数组下标相邻，而是数值相邻。

nums = [2, 2, 3, 3, 3, 4]
选 3：获得 9 分，但 2 和 4 都不能再选
选 2 和 4：获得 4 + 4 = 8 分

这个结构和“偷了第 i 家就不能偷第 i-1 家、第 i+1 家”完全一致。

二、为什么要先合并相同数字

如果决定选择数字 x，所有值为 x 的元素都应该一起拿。因为拿一个 x 已经会删除 x-1 和 x+1，继续拿其他 x 没有额外冲突，只会增加收益。

count[3] = 3
sum[3] = 3 * 3 = 9

合并后，原数组变成数值轴上的收益数组：

数值	2	3	4
总收益	4	9	4

记忆钩子：删除并获得点数，先把“数组题”压成“数值轴打家劫舍”。

三、状态定义和转移公式

定义：

dp[i] = 考虑数值 0..i 时能获得的最大点数

对数值 i 有两种选择：

不选 i：dp[i-1]
选 i：dp[i-2] + sum[i]

所以转移为：

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

这个公式和打家劫舍一模一样，只是房子的收益来自统计后的数值总收益。

四、用数字例子推演

nums = [3,4,2]：

sum[2] = 2
sum[3] = 3
sum[4] = 4

DP：

dp[2] = max(dp[1], dp[0]+2) = 2
dp[3] = max(dp[2], dp[1]+3) = 3
dp[4] = max(dp[3], dp[2]+4) = 6

答案是 6，对应选择 2 和 4。

五、代码模板

int deleteAndEarn(int[] nums) {
    int max = 0;
    for (int x : nums) max = Math.max(max, x);
    int[] sum = new int[max + 1];
    for (int x : nums) sum[x] += x;
    int prev2 = 0, prev1 = 0;
    for (int i = 0; i <= max; i++) {
        int cur = Math.max(prev1, prev2 + sum[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

这里直接用两个变量滚动，prev1 对应 dp[i-1]，prev2 对应 dp[i-2]。

六、数值范围很大时怎么处理

如果 nums 里的值很大，比如最大值是 10^9，但只有 1000 个数，就不能开长度 10^9 的数组。此时可以排序去重，只处理出现过的数值。

values = [2, 3, 10]
2 和 3 相邻，要按打家劫舍冲突处理
3 和 10 不相邻，可以直接累加关系处理

场景	推荐写法
最大值不大	统计数组 + 打家劫舍
最大值很大	HashMap 统计 + 排序去重

面试时先写数组版，追问时说明大范围优化，会显得思路完整。

七、常见误区与追问

误区：按原数组下标做打家劫舍。 冲突发生在数值相邻，不是位置相邻。
误区：相同数字只拿一个。 选择某个数字后，相同数字都应该合并收益一起拿。
误区：忘记处理数值断层。 排序去重写法中，不相邻数值之间没有冲突。
追问：为什么能转成打家劫舍？ 因为选择 x 会排斥 x-1 和 x+1，就是相邻状态互斥。
追问：空间能优化吗？ 数组版 DP 可以用两个变量滚动。
追问：如果有负数怎么办？ 原题通常是正整数；若有负收益，选择逻辑和初始化都要重新定义。

八、加强记忆

删除并获得点数的关键动作是“合并同值，再看数值轴”。同值全拿，相邻值互斥，于是 sum[i] 就是一间房子的价值，公式直接变成 max(不选 i, 选 i)。不要被原数组顺序带偏，真正的顺序是数字从小到大。

简化版

详细版