740. Delete And Earn

Medium

Description

給定整數陣列 nums，每次操作可以選擇一個 nums[i]，獲得 nums[i] 點數，但必須刪除所有等於 nums[i] - 1 和 nums[i] + 1 的元素。求能獲得的最大點數。

Example:

Input: nums = [3,4,2] Output: 6

Intuition#

將問題轉化為 House Robber：統計每個數字的總分，相鄰數字不能同時選。

先用陣列統計每個值出現的總點數 earn[v] = v * count(v)
選了值 v 就不能選 v-1 和 v+1，等同於 House Robber 問題
狀態轉移：dp[i] = max(dp[i-1], dp[i-2] + earn[i])

Approaches#

1: Bottom-Up DP with Array#

概念: 建立值域陣列，套用 House Robber 的 DP
時間複雜度: O(n + maxVal)
空間複雜度: O(maxVal)

class Solution {
    fun deleteAndEarn(nums: IntArray): Int {
        val maxVal = nums.max()
        val earn = IntArray(maxVal + 1)
        for (n in nums) earn[n] += n
        val dp = IntArray(maxVal + 1)
        dp[1] = earn[1]
        for (i in 2..maxVal) {
            dp[i] = maxOf(dp[i - 1], dp[i - 2] + earn[i])
        }
        return dp[maxVal]
    }
}

⭐2: Rolling Variables#

概念: 只依賴前兩個狀態，用兩個變數取代陣列
時間複雜度: O(n + maxVal)
空間複雜度: O(maxVal) (earn 陣列)

class Solution {
    fun deleteAndEarn(nums: IntArray): Int {
        val maxVal = nums.max()
        val earn = IntArray(maxVal + 1)
        for (n in nums) earn[n] += n
        var prev2 = 0
        var prev1 = earn[1]
        for (i in 2..maxVal) {
            val cur = maxOf(prev1, prev2 + earn[i])
            prev2 = prev1
            prev1 = cur
        }
        return prev1
    }
}

🔑 Takeaways#

Pattern: 問題轉化 — 將「刪除相鄰值」轉化為經典的 House Robber
關鍵技巧: 先聚合（統計每個值的總收益），再用熟悉的 DP 模式求解