解題說明
Delete and Earn
題目描述：給定一個整數陣列 nums，每次操作可以選擇一個元素 nums[i] 獲得其點數，但同時必須刪除所有等於 nums[i]-1 和 nums[i]+1 的元素。求能獲得的最大點數。
解題思路：此題可以轉化為 House Robber 問題。關鍵觀察：如果選了某個值 x，就必須選所有的 x（因為不選白不選），同時不能選 x-1 和 x+1。
- 統計每個值的總點數：
earn[x] = x * count(x)。 - 問題轉化為：在數值軸上，不能選相鄰的兩個值，求最大收益 — 這就是 House Robber。
- 用 DP：
dp[x] = max(dp[x-1], dp[x-2] + earn[x])。
C++ 解法
複雜度分析
時間複雜度：O(n + m) — n 為陣列長度（統計頻率），m 為最大值（DP 遍歷）。
空間複雜度：O(m) — earn 陣列大小為最大值 + 1。DP 部分只用 O(1) 空間。
虛擬碼
1. Find maxVal in nums
2. Create earn[0..maxVal], where earn[x] = x * count of x in nums
3. Apply House Robber DP:
a. prev2 = 0, prev1 = 0
b. For i from 1 to maxVal:
- curr = max(prev1, prev2 + earn[i])
- prev2 = prev1, prev1 = curr
4. Return prev1其他解法
排序 + 分組：先排序，將連續的數字分為一組，對每組獨立做 House Robber。適合值域很大但數字種類少的場景，避免開大陣列。時間 O(n log n)，空間 O(n)。
雜湊表 + 排序：用 map 統計頻率，按 key 排序後做 DP。邏輯相同但適用於稀疏分佈。
延伸思考
- 此題和 House Robber 的核心轉換是什麼？如何用一句話總結？
- 如果數字可以是負數，問題會如何變化？
- 如果規則改為「選了 x 後要刪除 x-2 到 x+2 範圍內的所有元素」，DP 轉移方程要如何修改？