Delete and Earn LeetCode solution in Python

1
class Solution:
2
    def deleteAndEarn(self, nums: List[int]) -> int:
3
        count = Counter(nums)
4
        m = max(nums)
5
        memo = {}
6

7
        def choose(num):
8
            if num > m:
9
                return 0
10
            if num not in count:
11
                count[num] = 0
12
            if num in memo:
13
                return memo[num]
14
            memo[num] = max(choose(num + 1), num * count[num] + choose(num + 2))
15
            return memo[num]
16

17
        return choose(1)
18

19

20
# time and space complexity
21
# n = max(nums)
22
# time: O(n)
23
# space: O(n)