Python Solution: House Robber Problem

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

• https://www.youtube.com/watch?v=ge_Fv2ZQAaE

Written with StackEdit.