Leetcode Solutions 详解 Delete and Earn（LeetCode 740）：从递归到空间优化的 5 种动态规划解法-育师

Leetcode Solutions 详解 Delete and Earn（LeetCode 740）：从递归到空间优化的 5 种动态规划解法

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文基于当前仓库 articles/delete-and-earn.md 的完整内容展开，系统讲解 LeetCode 740 题「Delete and Earn」的解题演进路径：从朴素递归、记忆化搜索，到两种自底向上 DP，再到 House Robber 数组变换与空间优化滚动变量，共 5 种解法逐层递进，并附复杂度对比与常见错误剖析。读完本篇，你能够掌握「把分组取值冲突问题归约为打家劫舍（House Robber）」这一经典建模技巧，并能在 Python、Java 等语言中写出可直接运行的实现；仓库中另有 python/0740-delete-and-earn.py 与 java/0740-delete-and-earn.java 两种语言级别的独立实现可作交叉印证。

一、问题定义与前置知识

题面规则：给定整数数组nums，每次操作选择一个整数x删除它并获得x点分数；但删除x的同时必须删除所有x - 1与x + 1。求最多能获得多少分数。

原文档列出的前置知识点是：

动态规划——理解如何从子问题构建解，熟悉 House Robber 模式（本仓库有对应文档 articles/house-robber.md，其核心递推为max(dfs(i + 1), nums[i] + dfs(i + 2))）；
哈希表——按 key 分组累加，为每个唯一数值预计算总分；
排序——把相同数值归组，使连续数值可被相邻处理。

理解本题的关键洞察是：选取数值x时，同一数值的所有出现必须一并结算（获得x的全部点数），代价是相邻数值x-1、x+1被强制删除。因此决策单位不是「元素」而是「数值组」，而数值组之间只有相差 1 的组才互相冲突——这正是 House Robber 的结构。

二、解法 1：朴素递归（O(2^n)）

思路：排序后相同值聚集成组。定义dfs(i)表示从索引i开始能获得的最大分数：

i越界返回0；
累加当前组nums[i]的全部出现，得到pick，并跳过该组；
「跳过当前组」的分支：dfs(new_i)；
「选取当前组」的分支：再跳过后继的nums[i] + 1组（它们会被删除），取pick + dfs(after_skipping)；
返回两条分支的最大值。

Python 实现（原文档完整代码）：

class Solution: def deleteAndEarn(self, nums: List[int]) -> int: nums.sort() def dfs(i): if i >= len(nums): return 0 cur = nums[i] pick = 0 while i < len(nums) and nums[i] == cur: pick += nums[i] i += 1 res = dfs(i) while i < len(nums) and nums[i] == 1 + cur: i += 1 res = max(res, pick + dfs(i)) return res return dfs(0)

Java 版本（结构完全一致，dfs(nums, i)通过参数传递数组）：

public class Solution { public int deleteAndEarn(int[] nums) { Arrays.sort(nums); return dfs(nums, 0); } private int dfs(int[] nums, int i) { if (i >= nums.length) return 0; int cur = nums[i], pick = 0; while (i < nums.length && nums[i] == cur) { pick += nums[i]; i++; } int res = dfs(nums, i); while (i < nums.length && nums[i] == cur + 1) { i++; } res = Math.max(res, pick + dfs(nums, i)); return res; } }

Go 版本展示了闭包递归的写法（var dfs func(i int) int自引用声明）：

func deleteAndEarn(nums []int) int { sort.Ints(nums) var dfs func(i int) int dfs = func(i int) int { if i >= len(nums) { return 0 } cur := nums[i] pick := 0 for i < len(nums) && nums[i] == cur { pick += nums[i] i++ } res := dfs(i) for i < len(nums) && nums[i] == cur+1 { i++ } res = max(res, pick+dfs(i)) return res } return dfs(0) }

时间复杂度：$O(2^n)$——每个数值组最多二分选择，无记忆化时指数爆炸；
空间复杂度：$O(n)$——递归栈深度。

该解法的价值在于确立了「分组 + 跳过相邻组」的转移骨架，也为下一节的记忆化提供了直接的改造点。

三、解法 2：自顶向下记忆化 DP（Top-Down）

思路：朴素递归存在大量重叠子问题（同一索引会被多次到达）。改进方式：

先建哈希表val：每个唯一数值 → 该数值所有出现之和（注意是+= num累加，而不是覆盖）；
取出唯一数值并排序得到nums（长度等于去重后规模）；
用memo = [-1] * len(nums)做记忆；
dfs(i)的转移：取当前组时，若nums[i] + 1 == nums[i+1]（后继是连续值）则跳到i + 2，否则跳到i + 1；结果为max(take, dfs(i + 1))。

class Solution: def deleteAndEarn(self, nums: List[int]) -> int: val = defaultdict(int) for num in nums: val[num] += num nums = sorted(list(set(nums))) memo = [-1] * len(nums) def dfs(i): if i >= len(nums): return 0 if memo[i] != -1: return memo[i] res = val[nums[i]] if i + 1 < len(nums) and nums[i] + 1 == nums[i + 1]: res += dfs(i + 2) else: res += dfs(i + 1) res = max(res, dfs(i + 1)) memo[i] = res return res return dfs(0)

Java 版本把val与memo提为成员字段，避免每次递归传参：

public class Solution { private Map<Integer, Integer> val; private int[] memo; public int deleteAndEarn(int[] nums) { val = new HashMap<>(); for (int num : nums) { val.put(num, val.getOrDefault(num, 0) + num); } List<Integer> uniqueNums = new ArrayList<>(val.keySet()); Collections.sort(uniqueNums); memo = new int[uniqueNums.size()]; Arrays.fill(memo, -1); return dfs(uniqueNums, 0); } private int dfs(List<Integer> nums, int i) { if (i >= nums.size()) return 0; if (memo[i] != -1) return memo[i]; int res = val.get(nums.get(i)); if (i + 1 < nums.size() && nums.get(i) + 1 == nums.get(i + 1)) { res += dfs(nums, i + 2); } else { res += dfs(nums, i + 1); } res = Math.max(res, dfs(nums, i + 1)); memo[i] = res; return res; } }

这里有一个细节值得注意：只有「后继是连续值」时才跳到i + 2。如果唯一值序列是[2, 5, 6]，选取2之后可以无缝衔接5（无冲突），转移仍是dfs(i + 1)。这个判断是记忆化正确性的关键。

时间复杂度：$O(n \log n)$（排序主导，递归每个唯一值只计算一次）；
空间复杂度：$O(n)$。

四、解法 3：自底向上 DP - I（右向左填表）

思路：Top-Down 天然可翻转为 Bottom-Up：对排序后的唯一值序列从右向左处理，dp[i]表示「从第i个唯一值开始能获得的最大分数」，dp表开n + 1大小，天然覆盖越界为 0 的基例。

class Solution: def deleteAndEarn(self, nums: List[int]) -> int: val = defaultdict(int) for num in nums: val[num] += num nums = sorted(list(set(nums))) dp = [0] * (len(nums) + 1) for i in range(len(nums) - 1, -1, -1): take = val[nums[i]] if i + 1 < len(nums) and nums[i + 1] == nums[i] + 1: take += dp[i + 2] else: take += dp[i + 1] dp[i] = max(dp[i + 1], take) return dp[0]

Java 版本：

public class Solution { public int deleteAndEarn(int[] nums) { Map<Integer, Integer> val = new HashMap<>(); for (int num : nums) val.put(num, val.getOrDefault(num, 0) + num); List<Integer> sortedNums = new ArrayList<>(val.keySet()); Collections.sort(sortedNums); int[] dp = new int[sortedNums.size() + 1]; for (int i = sortedNums.size() - 1; i >= 0; i--) { int take = val.get(sortedNums.get(i)); if (i + 1 < sortedNums.size() && sortedNums.get(i + 1) == sortedNums.get(i) + 1) { take += dp[i + 2]; } else { take += dp[i + 1]; } dp[i] = Math.max(dp[i + 1], take); } return dp[0]; } }

状态转移一句话概括：dp[i] = max(dp[i + 1], val[i] + dp[相邻则i+2否则i+1])，与解法 2 的dfs逐字对应，只是把「函数调用 + memo 数组」换成了「显式数组从后往前填」。

时间复杂度：$O(n \log n)$；
空间复杂度：$O(n)$。

五、解法 4：自底向上 DP - II（House Robber 数组变换）

这是本篇最重要的建模跳跃：不再围绕「唯一值下标」建表，而是直接以数值本身作下标。

求数组最大值m；
建dp数组，大小为m + 2（尾部多一位作哨兵，防止i + 2越界）；
遍历输入，dp[num] += num——此时dp[i]恰好等于数值i的总分（累加完成）；
从m - 1递减到1：dp[i] = max(dp[i + 1], dp[i + 2] + dp[i])；
返回dp[1]。

class Solution: def deleteAndEarn(self, nums: List[int]) -> int: m = max(nums) dp = [0] * (m + 2) for num in nums: dp[num] += num for i in range(m - 1, 0, -1): dp[i] = max(dp[i + 1], dp[i + 2] + dp[i]) return dp[1]

Java 版本：

public class Solution { public int deleteAndEarn(int[] nums) { int m = 0; for (int num : nums) m = Math.max(m, num); int[] dp = new int[m + 2]; for (int num : nums) dp[num] += num; for (int i = m - 1; i > 0; i--) { dp[i] = Math.max(dp[i + 1], dp[i + 2] + dp[i]); } return dp[1]; } }

变换后的转移式dp[i] = max(dp[i + 1], dp[i + 2] + dp[i])与 House Robber 的dp[i] = max(dp[i - 1], dp[i - 2] + money[i])完全同构：数值i与i+1在数值轴上天然相邻，「取i必须弃i+1」即「劫i必须弃i+1」。数值轴上的空洞（如 2 和 5 之间缺 3、4）对应 House Robber 中「门里没钱」，不会造成任何损失——这正是解法 3 里else: take += dp[i + 1]分支的自动体现：空缺位置的dp值会顺着dp[i+1]一路传递过来。

时间复杂度：$O(m + n)$，其中m为数组最大值、n为数组长度；
空间复杂度：$O(m)$。

当m与n同量级时（本题约束下m ≤ 10^4级别的小数值域），该解法的常数与实现简洁度都很优秀。仓库中的独立实现 python/0740-delete-and-earn.py 正是这一思路的正向遍历变体：它先建store[num]累加各值总分，再用正向 DP 式dp[i] = max(dp[i - 2] + store[i], dp[i - 1])从左向右填表，注释明确标注为 "House Robber Style, Time Complexity O(n)"，与上述反向填表互为镜像，可佐证该变换的多种等价写法：

# House Robber Style # Time Complexity O(n) # Space Complexity O(n) class Solution(object): def deleteAndEarn(self, nums): upperLimit = max(nums) + 1 store = [0] * upperLimit for num in nums: store[num] += num dp = [0] * upperLimit dp[1] = 1 * store[1] for i in range(2, upperLimit): dp[i] = max(dp[i - 2] + store[i], dp[i - 1]) return dp[-1]

六、解法 5：空间优化（滚动两个变量）

思路：唯一值序列的自底向上 DP 只依赖前两个状态，可用earn1（前前状态）与earn2（前一状态）两个变量压掉整个dp数组。从左向右扫描排序后的唯一值：

当前值与前一值连续（nums[i] == nums[i-1] + 1）：有冲突，earn2 = max(curEarn + earn1, earn2)；
不连续：无冲突，可自由叠加，earn2 = curEarn + earn2；
每次更新前先用temp保存旧earn2作为新的earn1。

class Solution: def deleteAndEarn(self, nums: List[int]) -> int: count = Counter(nums) nums = sorted(list(set(nums))) earn1, earn2 = 0, 0 for i in range(len(nums)): curEarn = nums[i] * count[nums[i]] if i > 0 and nums[i] == nums[i - 1] + 1: temp = earn2 earn2 = max(curEarn + earn1, earn2) earn1 = temp else: temp = earn2 earn2 = curEarn + earn2 earn1 = temp return earn2

Java 版本：

public class Solution { public int deleteAndEarn(int[] nums) { Map<Integer, Integer> count = new HashMap<>(); for (int num : nums) count.put(num, count.getOrDefault(num, 0) + num); List<Integer> uniqueNums = new ArrayList<>(count.keySet()); Collections.sort(uniqueNums); int earn1 = 0, earn2 = 0; for (int i = 0; i < uniqueNums.size(); i++) { int curEarn = count.get(uniqueNums.get(i)); if (i > 0 && uniqueNums.get(i) == uniqueNums.get(i - 1) + 1) { int temp = earn2; earn2 = Math.max(curEarn + earn1, earn2); earn1 = temp; } else { int temp = earn2; earn2 = curEarn + earn2; earn1 = temp; } } return earn2; } }

需要特别辨析：本解法中curEarn的来源是「计数 × 数值」（nums[i] * count[nums[i]]），而前文解法 2/3 的val表直接存「累加和」，两者等价但代码形态不同。仓库中的 Java 独立实现 java/0740-delete-and-earn.java 采用计数表 +numsList.get(i) * counter.get(...)求curEarn，且在不连续分支写成earnOne = earnTwo; earnTwo += curEarn;——与上文temp三行写法语义相同，只是省去了临时变量，说明滚动变量的写法在实践中存在多种等价形态：

class Solution { public int deleteAndEarn(int[] nums) { Map<Integer, Integer> counter = new HashMap<>(); for (int i = 0; i < nums.length; i++) { counter.put(nums[i], counter.getOrDefault(nums[i], 0) + 1); } List<Integer> numsList = new ArrayList<>(counter.keySet()); Collections.sort(numsList); int earnOne = 0; int earnTwo = 0; for (int i = 0; i < numsList.size(); i++) { int curEarn = numsList.get(i) * counter.get(numsList.get(i)); if (i > 0 && numsList.get(i) == numsList.get(i - 1) + 1) { int temp = earnTwo; earnTwo = Math.max(earnOne + curEarn, earnTwo); earnOne = temp; } else { earnOne = earnTwo; earnTwo += curEarn; } } return earnTwo; } }

时间复杂度：$O(n \log n)$（排序主导）；
空间复杂度：$O(n)$（哈希表与唯一值列表；DP 状态本身 $O(1)$）。

七、五种解法复杂度总览

解法	时间复杂度	空间复杂度	状态载体
1. 朴素递归	$O(2^n)$	$O(n)$	递归栈
2. 自顶向下记忆化	$O(n \log n)$	$O(n)$	`memo[i]`，按唯一值下标
3. 自底向上 DP - I	$O(n \log n)$	$O(n)$	`dp[i]`，按唯一值下标，右向左
4. House Robber 数组变换	$O(m + n)$	$O(m)$	`dp[i]`，按数值本身下标
5. 空间优化滚动变量	$O(n \log n)$	$O(n)$	`earn1 / earn2`两变量

（n为数组长度，m为数组最大值；解法 4 在小数值域下最优。）

八、常见错误（Common Pitfalls）

原文档专门归纳了三类高频错误，均直接命中本题的建模要点：

1. 只计一次，没有累加所有出现

选取数值x的收益来自全部出现，常见错误是把累加写成覆盖：

# Wrong: only counts one occurrence val[num] = num # Correct: sum all occurrences val[num] += num

2. 忘记跳过相邻值

选取x后，x-1与x+1全部被删除；若转移里不处理这个约束，会高估答案：

# Wrong: doesn't skip consecutive numbers res = val[nums[i]] + dfs(i + 1) # Correct: skip next if consecutive if nums[i] + 1 == nums[i + 1]: res = val[nums[i]] + dfs(i + 2) else: res = val[nums[i]] + dfs(i + 1)

3. 把非连续数值误当作相邻

只有差 1 的数值才冲突。例如 2 与 5 之间有空隙，两者可以都取；若不加条件判断而一律按 House Robber 相邻处理，会无谓丢分：

# Wrong: always treats as adjacent earn2 = max(curEarn + earn1, earn2) # Correct: check if actually consecutive if i > 0 and nums[i] == nums[i - 1] + 1: earn2 = max(curEarn + earn1, earn2) else: earn2 = curEarn + earn2 # No conflict, add freely