198. House Robber

Medium

Problem:

You are a professional burglar who can steal money from any house. However, due to security systems, you cannot rob two adjacent houses; you must skip at least one house between robberies. Each house has a certain amount of money, which is given as input. Your task is to output the largest amount of money you can steal without robbing adjacent houses.

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

https://leetcode.com/problems/house-robber/

What to learn:

• In Python, dictionaries (hash tables) didn't originally maintain the order of input, but since Python 3.7+, they do. However, to ensure order is maintained in earlier versions of Python, it's explicitly declared using collections.OrderedDict().

• To extract the last item from a dictionary, you can use the popitem() method.

Solution:

Bottom-up: Tabulation

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)
        
        dp = collections.OrderedDict()
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            dp[i] = max(dp[i -1], dp[i - 2] + nums[i])
        
        return dp.popitem()[1]