題目描述:給定一個整數陣列 nums,每次操作可以選擇一個元素 nums[i] 獲得其點數,但同時必須刪除所有等於 nums[i]-1 和 nums[i]+1 的元素。求能獲得的最大點數。
解題思路:此題可以轉化為 House Robber 問題。關鍵觀察:如果選了某個值 x,就必須選所有的 x(因為不選白不選),同時不能選 x-1 和 x+1。
earn[x] = x * count(x)。dp[x] = max(dp[x-1], dp[x-2] + earn[x])。時間複雜度: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。邏輯相同但適用於稀疏分佈。