Problem Statement
leetcode problem link
My Solution [TLE]
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
counter = Counter(nums)
def dp(i, counter):
if i == len(nums):
return 0
num = nums[i]
skip = dp(i + 1, copy.deepcopy(counter))
take = 0
if counter[num] > 0:
counter[num] -= 1
counter[num - 1] = 0
counter[num + 1] = 0
take = dp(i + 1, copy.deepcopy(counter)) + num
return max(skip, take)
return dp(0, counter)
Improved Algorithm
from collections import Counter
from functools import lru_cache
class Solution:
def deleteAndEarn(self, nums):
count = Counter(nums)
values = sorted(count.keys())
n = len(values)
@lru_cache(None)
def dp(i):
if i >= n:
return 0
# Option 1: skip current value
skip = dp(i + 1)
# Option 2: take current value
take = values[i] * count[values[i]]
if i + 1 < n and values[i + 1] == values[i] + 1:
take += dp(i + 2)
else:
take += dp(i + 1)
return max(skip, take)
return dp(0)
Editorial
Approach 1: Top-Down Dynamic Programming
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
points = defaultdict(int)
max_number = 0
# Precompute how many points we gain from taking an element
for num in nums:
points[num] += num
max_number = max(max_number, num)
@cache
def max_points(num):
# Check for base cases
if num == 0:
return 0
if num == 1:
return points[1]
# Apply recurrence relation
return max(max_points(num - 1), max_points(num - 2) + points[num])
return max_points(max_number)
Approach 2: Bottom-Up Dynamic Programming
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
points = defaultdict(int)
max_number = 0
# Precompute how many points we gain from taking an element
for num in nums:
points[num] += num
max_number = max(max_number, num)
# Declare our array along with base cases
max_points = [0] * (max_number + 1)
max_points[1] = points[1]
for num in range(2, len(max_points)):
# Apply recurrence relation
max_points[num] = max(max_points[num - 1], max_points[num - 2] + points[num])
return max_points[max_number]