Solution to LeetCode 740 Delete and Earn.
LeetCode 740
Delete and Earn (Medium). [link]
1] Bottom-up DP
class Solution(object):
def deleteAndEarn(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
houses = [0] * (max(nums) + 1)
for x in nums:
houses[x] += x
for i in range(2, len(houses)):
houses[i] = max(houses[i] + houses[i-2], houses[i-1])
return houses[len(houses)-1]
2] Bottom-up DP with 1D array
class Solution(object):
def deleteAndEarn(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
houses = [0] * (max(nums) + 1)
for x in nums:
houses[x] += x
n = len(houses)
pre, cur = houses[0], max(houses[0],houses[1])
for i in range(2, n):
pre, cur = cur, max(pre + houses[i], cur)
return cur
