740. Delete and Earn

──────────────────────────────────────────────────────────────────────

740. Delete and Earn

選一個數字 k 可以得到 k 分，但同時會刪掉陣列裡所有的 k（每個都給分）以及所有的 k-1 和 k+1。求最大總分。

思路

這個題目從題目本身的敘述其實滿容易猜到解法是透過動態規劃求解，比較困難的是要找到符合動態規劃的子問題。

題目給的條件是如果選定一個數字 k，其中如果有 n 個 k 那就可以獲得 k * n 的獎勵，但是就不能選擇 k - 1 以及 k + 1 的數字。而目標是要最大化可以得到的獎勵。

卡住的地方

動態規劃的題目，通常給的陣列中每個元素都是獨立事件，但是這個題目卻不是 —— 因為相同的數字 k 可以散落在這個陣列中的各處，也就是會需要來回在陣列中的各處去找到 k 並且剔除 k 前後的可能。

這就是這個題目比較困難的地方。首次解題時，我也想過了是不是可以用 Heap 來處理？還是要用回溯法來處理，但是都會卡在「陣列中的數字是散落在各地」這個問題。

關鍵在於看穿：陣列的「順序」和「位置」在這題完全沒有意義。 題目的規則只跟數值有關，不跟位置有關。所以卡住的原因不是解法難，是還在用「位置」的角度看題目。

換成用「數值」當索引

所以我還是仔細的觀察題目，題目給的第二個例子其實比較好幫助思考 nums = [2,2,3,3,3,4] —— 那就是如果陣列已經排列好的話，是不是可以一次把一樣的數字選取起來？

   [2, 2, 3, 3, 3, 4]
=> [4,    9,       4]

這時候這個題目就會比較容易想了！因為其實如果把數字 k 一起選起來，我們就知道可以跳過 k + 1。

但是上面這樣的做法也會有問題，因為如果題目是 [2, 2, 3, 3, 3, 5]，選了 3 之後 5 還是可以繼續選的。不過這沒問題 —— 只要以數值當索引、中間沒出現的數值就是 0 分，「跳過 k+1」這個規則自然就對了（跳過一個 0 分的格子不損失任何東西）。

觀察到此，其實這個題目就很類似 198. House Robber 了：當選擇偷第 k 個位置時，前後兩個位置的房子是不能去碰的。

因此只要能把題目給的形式轉換成 House Robber 的形式，就可以算出最大的獎勵了。我的做法是，原先陣列中有出現的數字都當作是 index，並且在該 index 中把獎勵都累積起來；至於陣列要多大，其實只要找到最大的數字即可。

解題方向

自底向上

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        
        m = max(nums) + 1
        
        rewards = [0] * m
        
        for num in nums:
            rewards[num] += num
            
        res = [0] * (len(rewards) + 1)

        res[1] = rewards[0]

        i = 2
        while i < len(rewards) + 1:
            res[i] = max(rewards[i - 1] + res[i - 2], res[i - 1])
            i += 1
            
        return res[-1]

rewards[num] += num 是整題的轉換核心：同一個數值的所有出現一次算完。之後 rewards 就是一排「房子」，res 完全照 198 的遞推跑。

res 比 rewards 多一格當虛擬起點，所以裡面要用 rewards[i-1]，索引偏移一格 —— 和 198 自底向上那版是同一種寫法。

遞迴（記憶化）

轉換完之後，遞迴版和 198 幾乎一字不差：

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        points = [0] * (max(nums) + 1)
        for x in nums:
            points[x] += x

        @cache
        def dp(i):
            if i >= len(points):
                return 0
            return max(dp(i + 1), points[i] + dp(i + 2))    # 不取 / 取了跳兩格
        return dp(0)

補充

為什麼不用追蹤「被刪掉」的值

轉換完之後，程式碼裡完全沒有「刪除」這個動作 —— 因為那條約束已經被遞迴的結構表達了，而且是兩邊各管一半：

刪掉誰	誰負責擋	怎麼擋
num + 1	被呼叫的那一層	取了 i 就跳到 dp(i + 2)，i + 1 在這條路上永遠不會被走到
num - 1	呼叫我的那一層	dp(i) 會被呼叫，就代表上一層沒有取 i - 1（取了的話它會跳到 dp(i + 1)，根本不會呼叫到我）

兩個方向各被擋一次，所以沒有人需要記住「誰被刪掉了」—— DP 選出來的數值集合不可能出現相鄰的兩個：

[2, 2, 3, 3, 3, 4]          -> 選了數值 [3]，總分 9
[3, 4, 2]                   -> 選了數值 [2, 4]，總分 6      ← 2 和 4 不相鄰，都能拿
[1, 1, 1, 2, 4, 5, 5, 5, 6] -> 選了數值 [1, 5]，總分 18

另外兩件事讓「刪除」不需要被追蹤：

取了 num 就一定會取光所有的 num。 拿掉一個 num 只會刪掉 num ± 1，其他相同的數字還在，所以拿完第一個之後剩下的都是免費的 —— 沒有理由不拿。這就是為什麼同一個數值的獎勵可以當成一個不可分割的原子，rewards[num] += num 那行就是在做這件事。

和 num 不相鄰的數值完全不受影響。 刪除只波及 num ± 1，所以除了「跳過隔壁」以外，沒有任何額外狀態要記 —— 這正是它能塌成一維 DP 的原因。

遞迴版有堆疊風險，而且原因和別題不同

遞迴版在 Python 預設的 recursionlimit = 1000 下會 RecursionError，而且遞迴深度取決於 max(nums)（LeetCode 上限 ${10}^4$），不是元素個數。

所以 [10000, 1] 這種只有兩個元素的輸入就會爆 —— 輸入只有兩個數字也會遞迴一萬層。這是這題和 198 最不一樣的地方（198 的深度就是房子數）。

所以在很大的數值範圍上，自底向上或滾動變數的迭代版比較不用擔心深度。

整個家族

題目	排列方式	「相鄰」是什麼	解法
198. House Robber	一排	陣列上相鄰	一維 DP
213. House Robber II	一環	首尾也相鄰	拆成兩條直線各跑一次
337. House Robber III	一棵樹	父子相鄰	後序遞迴，回傳 (偷, 不偷) 兩個值
740 這題	一排（按數值）	數值差 1	先轉換，再套 198

這題是家族裡唯一的換皮題 —— 難的不是 DP，是看出它就是 198。「不能同時選相鄰的兩個」這個訊號一出現就要想到這裡。

整理見 Dynamic Programming 模板。

複雜度

設 n 是陣列長度、M 是最大值。兩種寫法的複雜度相同。

自底向上 / 遞迴（記憶化）

• 時間 $O(n+M)$ — 統計 $O(n)$，DP 走過整個 rewards 是 $O(M)$
• 空間 $O(M)$ — rewards 和 res 兩個長度 M 的陣列；用滾動變數可以省掉 res，但 rewards 還在，所以仍然是 $O(M)$

值得注意的是 $M$（最大值）也會進到複雜度裡，而不只有 n。當數值稀疏且很大時（n 小但 M 大），這個做法就會很浪費 —— 面試被追問「如果數值範圍是 ${10}^9$ 呢」問的就是這件事。