删除并获得点数 图解题解

删除并获得点数到底在求什么

给一个数组 nums，每次挑一个值 x：删掉所有等于 x 的数、得分 x，代价是连带删光所有 x-1 和 x+1（不得分）。反复删空求最高总分。nums = [2,2,3,3,3,4,6,6] 的答案是 21：选值 3 三次拿 9 分、选值 6 两次拿 12 分，值 2、4 被连带清掉。

为什么每次选最大的会算错

最顺手的贪心（每步只挑眼前最好的、不顾以后）是每次选最大的值。可选大数会连累两边小数，选了 4 就废掉 3 那三个数。穷举也不行：每个值选或不选是两个分支，值域（所有可能出现的数值，本例 0 到 6）一大，方案数就指数级炸开，而后半段大量重复被反复重算。

为什么这题能变成打家劫舍

值 v 的总收益是 v 乘它的出现次数，扫一遍折进 sum 数组。本例 sum[2]=4、sum[3]=9、sum[4]=4、sum[6]=12，其余为 0。

把值域 0 到 6 排成一排，每格放 sum[v]。约束「选了 v 就不能选 v-1 和 v+1」，就是这排里选一个就不能选左右紧挨的邻居，跟打家劫舍一模一样：一排房子不能偷相邻两家。冲突只在数值相邻，跟它们在原数组排第几无关，按值排一排才对得上。

选了 v 为什么只能接 dp[v-2]

定义 dp[v] 为「只考虑值 0 到 v、不选相邻值时能拿的最大分」。到值 v 两种互斥选择：不选就继承 dp[v-1]；选 v 拿 sum[v]，但选了 v 排斥 v-1，不能接 dp[v-1]，只能接隔开一格的 dp[v-2]。取大，dp[v] = max(dp[v-1], dp[v-2] + sum[v])。

最容易写错的是选 v 时接成相邻的 dp[v-1]，等于让 v 和 v-1 同时被选。接 dp[v-2] 才跳过相邻那格。dp[v] 只依赖前两格，两个滚动变量就够。

拿题目样例把 dp 填一遍

sum = [0, 0, 4, 9, 4, 0, 12]，下标就是值。dp[0]=0、dp[1]=0。dp[2] 选 sum[2]=4 接 dp[0]=0 得 4。dp[3] 选 sum[3]=9 接 dp[1]=0 得 9。dp[4] 选 sum[4]=4 接 dp[2]=4 只有 8，不如不选继承的 9，取 9。dp[5] 值 5 没出现，选 0 接 dp[3]=9 得 9。dp[6] 选 sum[6]=12 接 dp[4]=9 得 21。最后 dp[6]=21 就是答案，对应值 3 加值 6，和题目吻合。

复杂度多少，sum 和防溢出两处别踩

统计 sum 扫原数组 O(n)，填 dp 扫值域 O(M)，M 为最大值，合起来 O(n+M)。sum 数组按值域开 O(M)，dp 两个变量滚动 O(1)。

两个坑：一是 sum[v] 存 v 乘次数的总得分，写成「出现次数」就把 9 分记成 3 个；二是次数多、值大时总分会超 int，C++ 和 Java 得用 long。还有个隐蔽点：值 5 这种没出现的空格也要填 dp，隔开值 4 和值 6，dp[6] 才接得到含选 3 的 dp[4]。

Python

class Solution:
    def deleteAndEarn(self, nums):
        if not nums:
            return 0
        mx = max(nums)
        total = [0] * (mx + 1)          # total[v] = v * 出现次数
        for v in nums:
            total[v] += v
        prev2, prev1 = 0, 0             # dp[v-2], dp[v-1]
        for v in range(mx + 1):
            cur = max(prev1, prev2 + total[v])   # 选 or 不选
            prev2, prev1 = prev1, cur
        return prev1

C++

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if (nums.empty()) return 0;
        int mx = *max_element(nums.begin(), nums.end());
        vector<long long> total(mx + 1, 0);  // total[v]=v*次数
        for (int v : nums) total[v] += v;
        long long prev2 = 0, prev1 = 0;      // dp[v-2], dp[v-1]
        for (int v = 0; v <= mx; v++) {
            long long cur = max(prev1, prev2 + total[v]);
            prev2 = prev1;
            prev1 = cur;
        }
        return (int)prev1;
    }
};

Java

class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums.length == 0) return 0;
        int mx = 0;
        for (int v : nums) mx = Math.max(mx, v);
        long[] total = new long[mx + 1];     // total[v]=v*次数
        for (int v : nums) total[v] += v;
        long prev2 = 0, prev1 = 0;           // dp[v-2], dp[v-1]
        for (int v = 0; v <= mx; v++) {
            long cur = Math.max(prev1, prev2 + total[v]);
            prev2 = prev1;
            prev1 = cur;
        }
        return (int) prev1;
    }
}