★ FEATURED ARTICLE 第一次在刷题网站看到“删除并获得点数”这道题时我下意识觉得它就是个数组模拟题遍历一遍遇到要删的就把相邻的删掉然后算个最大收益。真正动手写才发现这题根本不能顺着数组去模拟你随便选一个数连坐的是“数值上相邻”的数而不是“位置上相邻”的数。这个反直觉的设计让很多人一开始就把模型建错了。这篇笔记围绕动态规划、线性dp和C实现来写把这个题从题意到建模、从状态设计到边界处理完整拆一遍。LeetCode 740hot100动态规划里的常客洛谷题单里的线性DP模型也经常拿它当变体考。无论你是刚入门动态规划、正在准备面试还是单纯想看看这道题的C代码怎么写这篇都可以直接对照着看。1. 这道题为什么值得单独写一篇1.1 从“位置冲突”到“数值冲突”的认知转换先看题目给的操作规则你可以选择任意一个数nums[i]删除获得nums[i]的点数但同时必须删除所有等于nums[i]-1和nums[i]1的元素。注意这里的关键字是“所有”而且是按数值不按位置。比如数组[3, 4, 2]如果先选3那么所有等于2和4的数都必须删除哪怕数组里2和4根本不在3旁边。仔细想一下就会发现这个题目里的“相邻”不是索引上的相邻而是数值上的相邻。这是整道题最容易绕晕的地方也是它和其他数组删除类问题的本质区别。如果把视角从“位置”切换到“数值”问题就变成在一根数值轴上从1到maxVal排开每个数值可以通过删除操作被“选中”选中一个值i之后它会带走所有等于i的数获得i乘以频次的分同时锁定i-1和i1这两个数值让它们不能再被选。也就是说冲突发生在数值之间跟数组元素原来的排列顺序无关。这个认知一旦建立后面怎么建模都顺。1.2 几种典型错误思路我自己第一次做的时候踩了三个大坑估计很多初学者也会踩第一种是排序后当成打家劫舍。有人会先把数组排序然后判断相邻两个数是否相差1如果相差1就跳着取。这个思路方向是对的但忽略了重复值数组里可能有多个3每个3都能独立提供3分排序后只把3当成一个元素处理答案必然偏小。第二种是DFS回溯枚举删除顺序。每次递归选择删除哪个数然后模拟删除相邻数值再进入下一层。这个思路理论上能算出答案但状态太多n一大直接超时。题目数据规模到10^4指数级算法根本不可能过。第三种是贪心。每次都选当前数值最大的数删那就更经不起推敲了。举个反例数组[3, 3, 4]最大值是4贪心先删4得4分同时删掉所有3总分只有4。如果先删两个3得6分4也被删掉了总分6。贪心明显不是全局最优。这三种错误思路的共同根源是没有把“数值聚集”这个操作显式地做出来。一旦你先把每个数值能贡献的总点数统计清楚问题立刻变成一条一维DP的流水线。2. 建模的关键一步统计每个数值能贡献的总点数2.1 为什么是数值乘以出现次数题目只说删一个数得一个数的点数但别忘了你删掉一个3之后数组里剩下的3并不会被清除它们还在。你完全可以继续选下一个3再得3分直到所有3全部被你删完为止。也就是说只要最终决策里选中了数值3你会且只会获得“3的出现次数乘以3”这么多分。所以把输入数组的每个数值先做一次聚合sum[i] i * count(i)sum[i]表示“这一整轮操作中如果你决定选择数值i能从这个数值上拿到的总分”。这个聚合操作是整道题的灵魂。做了这一步原来乱糟糟的数组就变成了一根带权的数值轴每个下标i对应一个权重sum[i]。拿示例来说输入[2, 2, 3, 3, 3, 4]sum[2] 2 * 2 4sum[3] 3 * 3 9sum[4] 4 * 1 4其余下标都是0做完这一步你面对的不再是6个零散的数而是一排连续的“房子”每栋房子有固定金额的现金而且相邻编号的房子之间互相冲突。这个视角跟打家劫舍几乎一模一样只不过这里的“相邻房子”在数值上相邻而不是在数组位置上相邻。2.2 用数组还是用哈希表统计LeetCode 740的原题约束里nums[i]的取值范围是1到10^4所以最简单的方式就是直接开一个maxVal 1大小的数组遍历一遍把所有值塞进去vectorint sum(maxVal 1, 0); for (int x : nums) { sum[x] x; }这样统计完sum直接就是DP要用的“价值数组”连二次转换都省了。时间上遍历一次数组之后DP再扫一次值域总复杂度O(n maxVal)在10^4的值域下非常快。有人习惯用unordered_map先统计频次再手动乘以数值也可以但会比直接开数组多一些步骤。如果题目没有给值域上限或者值域特别大比如到10^9固定数组就行不通了得用哈希表加离散化的思路这部分我在第4章的离散化写法里单独说。2.3 为什么做完统计就不用管删除顺序了这是很多教程没讲透的地方为什么聚合之后就敢放心大胆地做DP了因为最终得分只取决于“最终选中了哪些数值”完全不取决于你选它们的先后顺序。你从数值集合S中拿到的总分就是所有sum[i]之和只要S里不存在相差1的两个数这个S就是合法的可选集合。反过来任何一个合法的“删除过程”对应的选中集合也一定满足这个不相邻条件。所以题目从一个操作序列问题变成了一个纯集合优化问题这才能用动态规划去解它。删除顺序、剩余元素、中间状态这些干扰项在聚合之后全部消失。3. 动态规划推导dp[i]到底代表什么3.1 状态定义与转移方程的由来现在我们把数值轴当作一维数组下标从1到maxVal每个位置i有它的收益sum[i]。目标是从中选出一组下标要求任意两个被选中的下标之差不能等于1使总收益最大。这已经是标准的一维线性DP模型了。定义dp[i] 只考虑数值 1 到 i能获得的最大点数考虑数值i时只有两种决策不选i那i-1选不选都无所谓直接继承dp[i-1]。选i获得sum[i]但i-1必须被放弃所以等于 sum[i] dp[i-2]。两者取较大dp[i] max(dp[i-1], dp[i-2] sum[i])边界条件dp[0] 0dp[1] max(dp[0], dp[-1] sum[1]) sum[1]因为数值1前面没有相邻值需要跳过。实际写代码时可以把dp数组从0开始存避免访问负下标。为什么选i的时候只看dp[i-2]而不用管i1因为我们在从头到尾递推i1还没进入视野等计算dp[i1]时DP会自己判断“如果选了i1那i就得放弃”这件事。这个“从左到右递推未来交给未来”的思路正是线性dp的基本套路。3.2 手动跑一遍完整例子拿上面的[2, 2, 3, 3, 3, 4]继续算sum[2] 4sum[3] 9sum[4] 4其余为0dp[0] 0dp[1] sum[1] 0dp[2] max(dp[1], dp[0] sum[2]) max(0, 0 4) 4dp[3] max(dp[2], dp[1] sum[3]) max(4, 0 9) 9dp[4] max(dp[3], dp[2] sum[4]) max(9, 4 4) 9答案9和题目预期一致。注意dp[3]之所以直接跳到了9是因为选了3之后2和4都不能选而4这个位置虽然本身值4但它必须在dp[4]这一步权衡“选了4丢掉3”是否划算——这里9 8所以结果为9。再看一个容易混淆的例子[3, 3, 4]sum[3] 6sum[4] 4。dp[3] 6dp[4] max(6, 0 4) 6答案6。这个例子能直观看出贪心选4的问题是最大数值不代表最大总收益因为数值3出现了两次它的聚合价值远超单个的4。聚合让每个数值的“分量”不再是1而是它的出现次数这一点一定要在脑子里刻住。3.3 为什么不是区间DP有些同学一看“删除一个数会连坐周边”会往区间DP上想觉得要枚举删除区间、合并子区间。其实完全用不上。区间DP的场景通常是某个连续段的删除结果会影响相邻段的合并比如戳气球、移除盒子这类题。但这里“删除”只是把i-1和i1从候选集合里排除并没有产生新的相邻关系也没有子段合并的过程。它就是一个线性选择问题从左到右递推就够了。这也是它出现在“hot100动态规划”和各类“线性dp题单”里的原因这个题是学习一维DP状态的绝佳样本因为它把“聚合预处理”和“简单状态转移”结合得很好没有背模板感真正考验你对模型的理解。4. C代码实现与三个容易写错的地方4.1 基础数组版完整代码下面这个版本可以直接在VSCode里新建一个cpp文件或者粘到在线判题环境跑#include vector #include algorithm using namespace std; class Solution { public: int deleteAndEarn(vectorint nums) { if (nums.empty()) return 0; int maxVal 0; for (int x : nums) { maxVal max(maxVal, x); } // sum[i] 表示数值 i 被选择时能贡献的总点数 vectorint sum(maxVal 1, 0); for (int x : nums) { sum[x] x; } // 线性DP vectorint dp(maxVal 1, 0); dp[1] sum[1]; for (int i 2; i maxVal; i) { dp[i] max(dp[i - 1], dp[i - 2] sum[i]); } return dp[maxVal]; } };这段代码的核心就两步聚合sum数组然后做线性DP。注意题目给的数据范围保证maxVal至少为1所以直接用dp[1]不会越界。如果想更防御可以在遍历后处理一个if (maxVal 1) return sum[1];但在原题约束下不是必需。4.2 滚动数组优化空间降到O(1)上面的dp数组其实只用到了前两个状态可以滚动优化连dp数组都省掉class Solution { public: int deleteAndEarn(vectorint nums) { int maxVal 0; for (int x : nums) maxVal max(maxVal, x); vectorint sum(maxVal 1, 0); for (int x : nums) sum[x] x; int prev2 0; // dp[i-2] int prev1 0; // dp[i-1] for (int i 1; i maxVal; i) { int cur max(prev1, prev2 sum[i]); prev2 prev1; prev1 cur; } return prev1; } };这个写法把边界处理也简化了i从1开始prev2和prev1初始都是0第一次循环cur max(0, 0 sum[1]) sum[1]正好就是dp[1]的值。迭代完maxVal之后prev1就是dp[maxVal]。空间上sum数组还是要保留但DP部分只用了两个int。4.3 大值域场景离散化写法如果题目改造成nums[i]可以到10^9显然不能开一亿长度的数组。这时要换思路只对“出现过的数值”做DP。思路是用哈希表统计每个数值的出现次数把所有出现过的数值排序然后在一个压缩后的序列上做DP。唯一需要注意的是相邻两个数值如果差1它们之间才冲突如果差大于1中间没有别的值那它们互不影响可以直接累加。#include vector #include unordered_map #include algorithm using namespace std; class Solution { public: int deleteAndEarn(vectorint nums) { unordered_maplong long, long long cnt; for (int x : nums) cnt[x]; vectorpairlong long, long long vals(cnt.begin(), cnt.end()); sort(vals.begin(), vals.end()); int n vals.size(); vectorlong long dp(n, 0); dp[0] vals[0].first * vals[0].second; for (int i 1; i n; i) { long long cur vals[i].first * vals[i].second; if (vals[i].first vals[i - 1].first 1) { // 相邻值冲突不能同时选 dp[i] max(dp[i - 1], (i 2 ? dp[i - 2] : 0) cur); } else { // 不相邻则直接累加 dp[i] dp[i - 1] cur; } } return n 0 ? dp[n - 1] : 0; } };这个版本我在面试时被追问过如果只是背基础版可能就被将了一军。离散化之后时间O(n log n)空间O(n)在大值域下是正解。平时刷题如果用的是LeetCode原题的约束基础版就够了但理解离散化能帮你把这类题目的模型吃得更透。4.4 三种实现方式对比实现版本时间复杂度空间复杂度适用场景基础数组版O(n maxVal)O(maxVal)值域受限如原题1e4滚动数组版O(n maxVal)O(maxVal)DP部分O(1)追求简洁或面试展示优化意识离散化版O(n log n)O(n)值域极大或数据稀疏DP部分滚动数组O(n maxVal)O(n)存sum数组版和滚动版都要先统计有一点我得提醒基础版看起来是O(maxVal)空间但实际上就这个题而言因为sum数组本身就占了O(maxVal)滚动数组省下的只是额外dp数组整体空间复杂度没变。面试时要主动说清楚这一点否则面试官会认为你在混淆空间复杂度的概念。5. 我踩过的坑和面试时的解题表演顺序5.1 三个隐藏比较深的坑第一个坑是统计sum时忘了乘以数值本身。我看到有人这样写for (int x : nums) sum[x];然后DP公式里的sum[i]就变成了频次。样例数据小的时候可能碰巧能过一旦某个数值重复次数多答案会错得离谱。统计频次没错但DP里必须把它转成“贡献点数”也就是sum[x] x而不是sum[x]。第二个坑是maxVal很小但代码无脑访问dp[1]。有些写法为了省事把dp[1] sum[1]当成固定边界如果输入数组最大值是0虽然原题约束不出现0但你已经把代码改成通用版本时dp[1]会越界。我习惯在最前面加一个if (nums.empty()) return 0;再顺手做一次maxVal 0的判断养成防御性编程的习惯面试时反而加分。第三个坑是先排序再做DP。这个坑特别隐蔽排序本身不改变sum数组的统计结果但有些人排序后直接在有序数组上做相邻判断写着写着就变成了打家劫舍那种“按位置跳”的dp。排序会让“数值重复”的聚合被忽略比如两个3本来要合并成6分排序后却被当成两个位置分别判断状态被割裂答案一定是错的。记住这题第一步永远是聚合不是排序。5.2 面试时推荐的回答顺序这道题见过很多算法背得很熟、一到面试就讲不清楚的人。我整理了一个讲解顺序不管面试官怎么追问照着这个顺序走基本稳先说清楚题目规则里的“相邻”是数值相邻不是位置相邻用一个例子说明比如[3,4,2]选3会删掉2和4。推出聚合思路每个数值i可以通过连续操作拿完所有等于i的元素总分是i乘以出现次数。点出模型聚合之后变成经典的“打家劫舍”线性DP选i则i-1不能选。给出状态转移方程dp[i] max(dp[i-1], dp[i-2] sum[i])并说明边界。最后写代码边写边念注释写完主动提一句“还可以滚动数组优化空间降为O(1)”。这个顺序的好处是从题意理解到模型识别到代码落地每一步都有明确理由不会给面试官一种背答案的感觉。5.3 同类题举一反三这题本质上和打家劫舍LeetCode 198共享同一个递推结构。打家劫舍是直接在数组位置上做不相邻选择而本题需要先完成“数值聚合”这一步。理解这个差异后下面这些变体看一眼就知道怎么做打家劫舍I直接在原数组上dp[i] max(dp[i-1], dp[i-2] nums[i])。打家劫舍II环形数组拆成两次线性DP分别去掉首元素和尾元素。如果题目改成“选i会连坐i-2和i2”递推会变成dp[i] max(dp[i-1], dp[i-3] sum[i])模型一样只是间隔从1变成2。如果改成“选i会删除所有i的倍数”那就是另一个模型了要往因数分解或状态压缩方向想。建议把这几道题放在一起刷用同一个模板去套你会发现线性DP的“模型识别”能力比“刷题数量”重要得多。回到这道题本身它最值得学习的不是十行C代码而是那个“先聚合再DP”的建模步骤。很多中等难度的动态规划题难的不是转移方程而是怎么把一个看似操作复杂的问题转化成干净的一维状态。我个人的经验是拿到这种题先别想代码先在纸上写清楚三件事操作规则的本质是什么、哪些信息可以被聚合、聚合后问题变成了什么模型。这三件事想明白代码基本就是水到渠成的事。
阅读完成 · 觉得有帮助？
