介紹一題利用轉化的方法來變成熟悉的DP問題

題目連結: 740. Delete and Earn

題目描述:給你一個整數陣列 nums。你需要執行以下操作多次，以獲得最大點數：

選擇 nums 中的任何一個數字 nums[i]，你將獲得 nums[i] 點。

之後，你必須刪除所有等於 nums[i] - 1 和 nums[i] + 1 的元素。

返回你能獲得的最大點數。

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

Example 2:
Input: nums = [2,2,3,3,3,4]
Output: 9

Python

解題思路:這個問題的規則「選了 num，就不能選 num-1 和 num+1」，和「House Robber」中「偷了第 i 間房，就不能偷第 i-1 間」的規則是一樣的!

我們首先需要將原始的 nums 陣列（數字可能重複且無序），轉化成一個有序適合 DP 的形式。

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        temp = [0]*(max(nums)+1)
        for i in nums:
            temp[i]+=i
        pre1 = 0
        pre2 = 0
        for j in temp:
            curr = max(pre1,pre2+j)
            pre2, pre1 = pre1, curr
        return pre1

演算法分析:

• temp陣列是紀錄i值總共有多少(ex:如果3出現3次就是9)
• nums = [3, 4, 2] 會被轉化為 temp = [0, 0, 2, 3, 4]。
• temp陣列的形式與「House Robber」解的問題是一樣的。
• curr = max(pre1, pre2 + j):在考慮數字 j 時，我們做出選擇，不取 j (pre1)：那麼最高點數就是考慮到 j-1 時的最高點數;取 j (pre2 + j)：那麼我們就不能取 j-1，總點數等於 j 的點數，加上考慮到 j-2 時的最高點數。
• pre2, pre1 = pre1, curr將[j-1]值先賦予[j-2]，再將curr值賦予[j-1]。

複雜度分析:

• 時間複雜度為 O(n+m)(n 是原始陣列 nums 的長度，而 m 是 nums 中的最大值)。
  1. max(nums)找到陣列中的最大值，需要遍歷一次 nums，時間複雜度為 O(n)。
  2. temp = [0]*(max(nums)+1)建立一個長度為 m+1 的陣列，時間複雜度為 O(m)。
• 空間複雜度： O(n)(空間複雜度由 temp 陣列大小n決定)。

有問題可以底下留言!
下回見!!