Leetcode Solutions 详解 Delete and EarnLeetCode 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、x1被强制删除。因此决策单位不是「元素」而是「数值组」而数值组之间只有相差 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] cur1 { i } res max(res, pickdfs(i)) return res } return dfs(0) }时间复杂度$O(2^n)$——每个数值组最多二分选择无记忆化时指数爆炸空间复杂度$O(n)$——递归栈深度。该解法的价值在于确立了「分组 跳过相邻组」的转移骨架也为下一节的记忆化提供了直接的改造点。三、解法 2自顶向下记忆化 DPTop-Down思路朴素递归存在大量重叠子问题同一索引会被多次到达。改进方式先建哈希表val每个唯一数值 → 该数值所有出现之和注意是 num累加而不是覆盖取出唯一数值并排序得到nums长度等于去重后规模用memo [-1] * len(nums)做记忆dfs(i)的转移取当前组时若nums[i] 1 nums[i1]后继是连续值则跳到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 MapInteger, 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); } ListInteger uniqueNums new ArrayList(val.keySet()); Collections.sort(uniqueNums); memo new int[uniqueNums.size()]; Arrays.fill(memo, -1); return dfs(uniqueNums, 0); } private int dfs(ListInteger 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) { MapInteger, Integer val new HashMap(); for (int num : nums) val.put(num, val.getOrDefault(num, 0) num); ListInteger 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[相邻则i2否则i1])与解法 2 的dfs逐字对应只是把「函数调用 memo 数组」换成了「显式数组从后往前填」。时间复杂度$O(n \log n)$空间复杂度$O(n)$。五、解法 4自底向上 DP - IIHouse Robber 数组变换这是本篇最重要的建模跳跃不再围绕「唯一值下标」建表而是直接以数值本身作下标。求数组最大值m建dp数组大小为m 2尾部多一位作哨兵防止i 2越界遍历输入dp[num] num——此时dp[i]恰好等于数值i的总分累加完成从m - 1递减到1dp[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与i1在数值轴上天然相邻「取i必须弃i1」即「劫i必须弃i1」。数值轴上的空洞如 2 和 5 之间缺 3、4对应 House Robber 中「门里没钱」不会造成任何损失——这正是解法 3 里else: take dp[i 1]分支的自动体现空缺位置的dp值会顺着dp[i1]一路传递过来。时间复杂度$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 earn2Java 版本public class Solution { public int deleteAndEarn(int[] nums) { MapInteger, Integer count new HashMap(); for (int num : nums) count.put(num, count.getOrDefault(num, 0) num); ListInteger 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) { MapInteger, Integer counter new HashMap(); for (int i 0; i nums.length; i) { counter.put(nums[i], counter.getOrDefault(nums[i], 0) 1); } ListInteger 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] num2. 忘记跳过相邻值选取x后x-1与x1全部被删除若转移里不处理这个约束会高估答案# Wrong: doesnt 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九、小结与延伸阅读本篇的完整脉络是排序分组 → 发现「取组必弃相邻组」的冲突结构 → 递归建模 → 记忆化去重 → 自底向上填表 → 以数值为下标归约成 House Robber → 滚动变量压空间。核心可迁移的经验有两点「每个数值必须整体结算 相邻数值互斥」的题型如本题、House Robber 变体都可先做值域累加再套不相邻选取的 DP 模板转移中「连续与否」的判断nums[i] 1 nums[i 1]是分叉点缺失它是最常见的正确性错误。延伸资料仓库内相对路径原始题解文档articles/delete-and-earn.mdHouse Robber 模式文档本题的母题articles/house-robber.mdPython 参考实现House Robber 正向 DP 风格python/0740-delete-and-earn.pyJava 参考实现空间优化滚动变量java/0740-delete-and-earn.java仓库说明多语言题解覆盖与贡献方式README.md【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Leetcode Solutions 详解 Delete and Earn（LeetCode 740）：从递归到空间优化的 5 种动态规划解法
Leetcode Solutions 详解 Delete and EarnLeetCode 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、x1被强制删除。因此决策单位不是「元素」而是「数值组」而数值组之间只有相差 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] cur1 { i } res max(res, pickdfs(i)) return res } return dfs(0) }时间复杂度$O(2^n)$——每个数值组最多二分选择无记忆化时指数爆炸空间复杂度$O(n)$——递归栈深度。该解法的价值在于确立了「分组 跳过相邻组」的转移骨架也为下一节的记忆化提供了直接的改造点。三、解法 2自顶向下记忆化 DPTop-Down思路朴素递归存在大量重叠子问题同一索引会被多次到达。改进方式先建哈希表val每个唯一数值 → 该数值所有出现之和注意是 num累加而不是覆盖取出唯一数值并排序得到nums长度等于去重后规模用memo [-1] * len(nums)做记忆dfs(i)的转移取当前组时若nums[i] 1 nums[i1]后继是连续值则跳到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 MapInteger, 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); } ListInteger uniqueNums new ArrayList(val.keySet()); Collections.sort(uniqueNums); memo new int[uniqueNums.size()]; Arrays.fill(memo, -1); return dfs(uniqueNums, 0); } private int dfs(ListInteger 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) { MapInteger, Integer val new HashMap(); for (int num : nums) val.put(num, val.getOrDefault(num, 0) num); ListInteger 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[相邻则i2否则i1])与解法 2 的dfs逐字对应只是把「函数调用 memo 数组」换成了「显式数组从后往前填」。时间复杂度$O(n \log n)$空间复杂度$O(n)$。五、解法 4自底向上 DP - IIHouse Robber 数组变换这是本篇最重要的建模跳跃不再围绕「唯一值下标」建表而是直接以数值本身作下标。求数组最大值m建dp数组大小为m 2尾部多一位作哨兵防止i 2越界遍历输入dp[num] num——此时dp[i]恰好等于数值i的总分累加完成从m - 1递减到1dp[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与i1在数值轴上天然相邻「取i必须弃i1」即「劫i必须弃i1」。数值轴上的空洞如 2 和 5 之间缺 3、4对应 House Robber 中「门里没钱」不会造成任何损失——这正是解法 3 里else: take dp[i 1]分支的自动体现空缺位置的dp值会顺着dp[i1]一路传递过来。时间复杂度$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 earn2Java 版本public class Solution { public int deleteAndEarn(int[] nums) { MapInteger, Integer count new HashMap(); for (int num : nums) count.put(num, count.getOrDefault(num, 0) num); ListInteger 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) { MapInteger, Integer counter new HashMap(); for (int i 0; i nums.length; i) { counter.put(nums[i], counter.getOrDefault(nums[i], 0) 1); } ListInteger 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] num2. 忘记跳过相邻值选取x后x-1与x1全部被删除若转移里不处理这个约束会高估答案# Wrong: doesnt 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九、小结与延伸阅读本篇的完整脉络是排序分组 → 发现「取组必弃相邻组」的冲突结构 → 递归建模 → 记忆化去重 → 自底向上填表 → 以数值为下标归约成 House Robber → 滚动变量压空间。核心可迁移的经验有两点「每个数值必须整体结算 相邻数值互斥」的题型如本题、House Robber 变体都可先做值域累加再套不相邻选取的 DP 模板转移中「连续与否」的判断nums[i] 1 nums[i 1]是分叉点缺失它是最常见的正确性错误。延伸资料仓库内相对路径原始题解文档articles/delete-and-earn.mdHouse Robber 模式文档本题的母题articles/house-robber.mdPython 参考实现House Robber 正向 DP 风格python/0740-delete-and-earn.pyJava 参考实现空间优化滚动变量java/0740-delete-and-earn.java仓库说明多语言题解覆盖与贡献方式README.md【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考