Skip to main content

740. Delete and Earn

https://leetcode.com/problems/delete-and-earn/

Python​

DP with decreasing tuple (Time Limit Exceed)​

from functools import cache


class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        result = self.travel(tuple(nums))
        return result

    @cache
    def travel(self, nums):
        if not nums:
            return 0

        result = 0
        for i in range(len(nums)):
            pick_num = nums[i]
            rest = [num for num in nums[:i]+nums[i+1:] if num != pick_num+1 and num != pick_num-1]
            result = max(result, self.travel(tuple(rest))+pick_num)

        return result

Top-Down DP​

  • Official Solution
from collections import Counter
from functools import cache


class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        counts = Counter(nums)
        max_num = max(counts.keys())

        @cache
        def travel(num):
            if num == 0:
                return 0
            if num == 1:
                return counts[1]

            return max(
                travel(num-1),
                travel(num-2)+num*counts[num]
            )
        return travel(max_num)