删除并获得点数 图解题解

这道题到底在问什么

nums

[2,2,3,3,3,4,6,6]

输出

21

解释

选 3 三次(9)+选 6 两次(12)=21，2 和 4 被连带删光

先想最直接的笨办法

先一遍统计 total，再一遍线性填 dp，每格只看前两格，整体线性，比指数枚举快到天上去。（动画第 26 步）

最优解：一步一步想明白

1. 3贪心地「每次选当前最大的」会出错：选大数可能丢掉两边一堆小数。这种「选了就排斥邻居」的味道，得换个角度看。
2. 4选值 v，能拿的分 = v × 它出现的次数。我们先扫一遍原数组，把「有几个」一次性折叠进 total[v]。下面看着它一格一格累出来。
3. 5指针停在起点下面这排是原数组。指针从最左往右走，每碰到一个数 v，就把它的得分 v 加到右边 total[v] 上。盯住右边累计值怎么涨。
4. 6total[2] += 2第一个数是 2，把 2 加进 total[2]，它从 0 变 2。指针继续右移。
5. 7total[2] += 2又是一个 2，total[2] 再加 2 变成 4——这就是「两个 2 一起拿 = 4 分」被折叠进了一格。
6. 8total[3] += 3轮到第一个 3，给 total[3] 加 3。值 2 那两格已经扫完(变灰)。
7. 9total[3] += 3第二个 3，total[3] 涨到 6。三个 3 还差最后一个。
8. 10total[3] += 3第三个 3 加完，total[3] 到 9——选值 3 一次性能拿 9 分。
9. 11total[4] += 4数到 4，给 total[4] 加 4。它紧挨着 3，选 3 就会把它清掉。
10. 12total[6] += 6第一个 6 入账，total[6] 变 6。注意 6 和前面的 4 之间隔着个 5，互不相邻。
11. 13total[6] += 6最后一个 6 加完，total[6] 到 12——两个 6 折成一格 12 分。整个数组扫完，统计阶段结束。
12. 14把值域 0~6 排成一排，每格放它的 total[v]。选一个格子就不能选它左右紧挨着的格子——这完全等价于打家劫舍(不能偷相邻两家)！
13. 15下标=值，柱高=total[v]把刚统计的 total 摆成柱子：下标 0~6 就是值，柱高就是 total[v]。值 5 没出现(柱高 0)，它把 4 和 6 隔开，于是选 3 又选 6 互不冲突。开始填表。
14. 16dp[v] 表示「只考虑值 0..v 时能拿的最大分」。要么不选 v(继承 dp[v-1])，要么选 v(拿 total[v]，但只能接 dp[v-2])。两者取大。
15. 17dp[v] = 考虑值 0..v 的最大分上一行是 total，下一行是要填的 dp。dp[v] 的含义：只在值 0..v 里挑、且不挑相邻值，能拿的最大分。
16. 18dp[0] = total[0] = 0只有值 0 可选时，最大分就是它自己的 total[0]=0(本例没有 0)。这是不依赖别人的地基，第一格填好。
17. 19dp[1] = max(dp[0], total[1])考虑值 0、1：要么不选 1(拿 dp[0]=0)，要么选 1(拿 total[1]=0)。两者都是 0，dp[1]=0。第二格填好。
18. 20dp[2] = max(dp[1], dp[0]+total[2])到值 2：不选继承相邻的 dp[1]=0；选就拿 total[2]=4，但不能接相邻 dp[1]，只能接隔开的 dp[0]=0 → 得 4。取大，dp[2]=4。
19. 21dp[3] = max(dp[2], dp[1]+total[3])到值 3：不选继承 dp[2]=4；选拿 total[3]=9，跳过相邻 dp[2]，接 dp[1]=0 → 得 9。9 > 4，dp[3]=9。选 3 比保住 2 更划算。
20. 22dp[4] = max(dp[3], dp[2]+total[4])到值 4：不选继承 dp[3]=9；选拿 total[4]=4，接 dp[2]=4 → 共 8。9 > 8，dp[4]=9——选 4 反而因放弃 3 而变少，所以保住 3。
21. 23dp[5] = max(dp[4], dp[3]+total[5])值 5 没出现，total[5]=0。不选继承 dp[4]=9；选它拿 0、接 dp[3]=9，也是 9。dp[5]=9 保持不变——但这一格很重要，它把 4 和 6 隔开，让 6 能接到含 3 的状态。
22. 24dp[6] = max(dp[5], dp[4]+total[6])到值 6：不选继承 dp[5]=9；选拿 total[6]=12，跳过相邻 dp[5]，接 dp[4]=9(里头含了选 3 的 9 分)→ 共 21。21 > 9，dp[6]=21。这就是「选 3 又选 6」被表达了出来。
23. 25答案 = dp[6] = 21dp 这一行滚到最后一格 dp[6]=21 就是答案。对应方案：选值 3(9 分)+ 选值 6(12 分)，它们隔得远不冲突。和示例答案 21 对上了。
24. 26先一遍统计 total，再一遍线性填 dp，每格只看前两格，整体线性，比指数枚举快到天上去。
25. 29约束是「选了 v 不能选 v±1」，冲突发生在数值相邻上，跟它们在原数组的位置无关。所以把值排成一排来 DP，先排序去重也行。
26. 31选 3 时误接 dp[2]=4如果选值 3 时去接相邻的 dp[2]=4，算出 13——可这相当于同时拿了值 2 和值 3，而它们相邻、本该互斥。正确写法是接 dp[v-2]，跳过相邻那格。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

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;
    }
};

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;
    }
}

复杂度

面试官可能追问