class Solution(object):
def __init__(self):
self.maxVal = 0
self.lookup = {}
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
if len(nums) >= 2:
self.lookup[0] = nums[0]
self.lookup[1] = max(nums[0], nums[1])
for index in range(2, len(nums)):
# There are two options at each house: choose or not choose
#
houseSelected = nums[index] + self.lookup[index - 2]
houseNotSelected = self.lookup[index - 1]
result = max(houseSelected, houseNotSelected)
self.lookup[index] = result
# We don't need to keep cache for previous to previous entries
del self.lookup[index - 2]
return self.lookup[len(nums) - 1]
References
Written with StackEdit.