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

Written with StackEdit.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: