题目描述
思路解析
一句话答案：LeetCode 740 删除并获得点数：选一个值 x 就得删光所有 x-1 和 x+1，冲突只在数值相邻。先把每个值的总收益折进 sum 数组，就化归成打家劫舍——相邻的值不能同选。线性填 dp，时间 O(n+M)、空间 O(1)。
删除并获得点数到底在求什么
给一个数组 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]。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
贪心地「每次选当前最大的」会出错：选大数可能丢掉两边一堆小数。这种「选了就排斥邻居」的味道，得换个角度看。
选值 v，能拿的分 = v × 它出现的次数。我们先扫一遍原数组，把「有几个」一次性折叠进 total[v]。下面看着它一格一格累出来。
第一步 · 扫原数组统计 total：下面这排是原数组。指针从最左往右走，每碰到一个数 v，就把它的得分 v 加到右边 total[v] 上。盯住右边累计值怎么涨。
扫到 nums[0] = 2：第一个数是 2，把 2 加进 total[2]，它从 0 变 2。指针继续右移。
扫到 nums[1] = 2：又是一个 2，total[2] 再加 2 变成 4——这就是「两个 2 一起拿 = 4 分」被折叠进了一格。
扫到 nums[2] = 3：轮到第一个 3，给 total[3] 加 3。值 2 那两格已经扫完(变灰)。
扫到 nums[3] = 3：第二个 3，total[3] 涨到 6。三个 3 还差最后一个。
扫到 nums[4] = 3：第三个 3 加完，total[3] 到 9——选值 3 一次性能拿 9 分。
扫到 nums[5] = 4：数到 4，给 total[4] 加 4。它紧挨着 3，选 3 就会把它清掉。
扫到 nums[6] = 6：第一个 6 入账，total[6] 变 6。注意 6 和前面的 4 之间隔着个 5，互不相邻。
扫到 nums[7] = 6：最后一个 6 加完，total[6] 到 12——两个 6 折成一格 12 分。整个数组扫完，统计阶段结束。
把值域 0~6 排成一排，每格放它的 total[v]。选一个格子就不能选它左右紧挨着的格子——这完全等价于打家劫舍(不能偷相邻两家)！
值域排成一排：把刚统计的 total 摆成柱子：下标 0~6 就是值，柱高就是 total[v]。值 5 没出现(柱高 0)，它把 4 和 6 隔开，于是选 3 又选 6 互不冲突。开始填表。
dp[v] 表示「只考虑值 0..v 时能拿的最大分」。要么不选 v(继承 dp[v-1])，要么选 v(拿 total[v]，但只能接 dp[v-2])。两者取大。
建表 · dp 行待填：上一行是 total，下一行是要填的 dp。dp[v] 的含义：只在值 0..v 里挑、且不挑相邻值，能拿的最大分。
地基 · 填 dp[0]：只有值 0 可选时，最大分就是它自己的 total[0]=0(本例没有 0)。这是不依赖别人的地基，第一格填好。
地基 · 填 dp[1]：考虑值 0、1：要么不选 1(拿 dp[0]=0)，要么选 1(拿 total[1]=0)。两者都是 0，dp[1]=0。第二格填好。
填 dp[2] · 第一次真选择：到值 2：不选继承相邻的 dp[1]=0；选就拿 total[2]=4，但不能接相邻 dp[1]，只能接隔开的 dp[0]=0 → 得 4。取大，dp[2]=4。
填 dp[3] · 关键一格：到值 3：不选继承 dp[2]=4；选拿 total[3]=9，跳过相邻 dp[2]，接 dp[1]=0 → 得 9。9 > 4，dp[3]=9。选 3 比保住 2 更划算。
填 dp[4]：到值 4：不选继承 dp[3]=9；选拿 total[4]=4，接 dp[2]=4 → 共 8。9 > 8，dp[4]=9——选 4 反而因放弃 3 而变少，所以保住 3。
填 dp[5] · 空格也要填：值 5 没出现，total[5]=0。不选继承 dp[4]=9；选它拿 0、接 dp[3]=9，也是 9。dp[5]=9 保持不变——但这一格很重要，它把 4 和 6 隔开，让 6 能接到含 3 的状态。
填 dp[6] · 最后一格：到值 6：不选继承 dp[5]=9；选拿 total[6]=12，跳过相邻 dp[5]，接 dp[4]=9(里头含了选 3 的 9 分)→ 共 21。21 > 9，dp[6]=21。这就是「选 3 又选 6」被表达了出来。
填表完成：dp 这一行滚到最后一格 dp[6]=21 就是答案。对应方案：选值 3(9 分)+ 选值 6(12 分)，它们隔得远不冲突。和示例答案 21 对上了。
先一遍统计 total，再一遍线性填 dp，每格只看前两格，整体线性，比指数枚举快到天上去。
约束是「选了 v 不能选 v±1」，冲突发生在数值相邻上，跟它们在原数组的位置无关。所以把值排成一排来 DP，先排序去重也行。
雷区实演 · 接错相邻格：如果选值 3 时去接相邻的 dp[2]=4，算出 13——可这相当于同时拿了值 2 和值 3，而它们相邻、本该互斥。正确写法是接 dp[v-2]，跳过相邻那格。
边界三连：注意「全相同」不是相邻冲突——3 和 3 是同一个值，选它就把所有 3 一起拿了，反而该全要。
面试追问：把「它就是打家劫舍」一句话讲透，再补一句值域过大时的排序变体，是这题的加分点。
参考代码
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复杂度
- 时间复杂度：O(n + M)，n=数组长度(统计 total)，M=最大值(扫一遍值域填 dp)，各一趟
- 空间复杂度：O(M)，total 数组按值域大小开；dp 用两个滚动变量 → O(1)，合计 O(M)
易错点
面试追问把动画讲成自己的话
追问这题和打家劫舍到底什么关系？
追问值域很大(比如到 1e9)但元素很少怎么办？
追问复杂度？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大加号标志
LeetCode 764 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题