删除并获得点数
Delete and Earn
题目详情
问题：删除并获得点数
考察：数组、哈希表、动态规划
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/delete-and-earn
英文原题
Problem: Delete and Earn
Patterns: Array, Hash Table, Dynamic Programming
Recency: 2yr
Link: https://leetcode.com/problems/delete-and-earn
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：把相同数字的贡献合并成 points[x] = x * count[x]。选择 x 就不能选择 x-1 和 x+1，问题转化为 House Robber，在数值轴上做动态规划。
复杂度：设最大值为 M，时间 O(n+M)，空间可 O(M) 或排序后 O(u)。
英文解析
Approach: Aggregate equal numbers into `points[x] = x * count[x]`. Choosing `x` forbids `x-1` and `x+1`, so the problem becomes House Robber on the value axis.
Complexity: Time or after sorting unique values; space or .