動機

想像要自由一點

Problem

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

  • Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.

Return the maximum number of points you can earn by applying the above operation some number of times.

 

Example 1:

Input: nums = [3,4,2]Output: 6Explanation: You can perform the following operations:- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].- Delete 2 to earn 2 points. nums = [].You earn a total of 6 points.

Example 2:

Input: nums = [2,2,3,3,3,4]Output: 9Explanation: You can perform the following operations:- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].- Delete a 3 again to earn 3 points. nums = [3].- Delete a 3 once more to earn 3 points. nums = [].You earn a total of 9 points.

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 104

sol1

定義dp是從i開始拿可以拿到的最高分數

class Solution:
    @cache
    def dp(self, i):
        if i >= len(self.keys):
            return 0
        
        n = self.keys[i]
        return n * self.nums[n] + max([self.dp(j) for j in range(i+1, len(self.keys)) if self.keys[j] - n > 1], default=0)
    def deleteAndEarn(self, nums: List[int]) -> int:
        self.nums = Counter(nums)
        self.keys = sorted(list(self.nums.keys()))
        return max(self.dp(i) for i in range(len(self.keys)))

sol2

sol1會過，但很慢

這個時候要發散一下思維，如果把分數當成房子，不存在的就當成房子沒得搶，這下就變成house robber

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        nums = Counter(nums)
        dp = [0] * (1+max(nums.keys()))
        for i in range(1,len(dp)):
            dp[i] = max(dp[i-1], nums[i]*i + (dp[i-2] if i >= 2 else 0))
        return dp[-1]