House Robber

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

Example of dp.

Intuition, when robbed the first house, or we skipped it, the problem is reduced…

Approach 1: Memoization

dp: dict[int, int] = {}
n = len(nums)
 
def rob_from(i):
    if i >= n:
        return 0
 
    if i in dp:
        return dp[i]
 
    ans = max(
        rob_from(i + 1),
        rob_from(i + 2) + nums[i]
    )
 
    dp[i] = ans
    return ans
 
return rob_from(0)

Approach 2: DP

A tabular approach isn’t necessarily “bottom-up”!

n = len(nums)
max_amount = [None] * (n + 1)
 
max_amount[n] = 0  # no house left, cannot obtain more money
max_amount[n - 1] = nums[n - 1]  # one house left, rob it
 
for i in range(n - 2, -1, -1):
    # rob from i-th house, i included
    max_amount[i] = max(
        max_amount[i + 1],  # don't rob this, rob next
        max_amount[i + 2] + nums[i]  # rob this and second next
    )
 
return max_amount[0]

Approach 3: Optimized DP

Observe that max_amount[i] only depends on the previous two values at i + 1 and i + 2. Space complexity also optimized.

n = len(nums)
rob_next_next = 0  # there's no next next, no house left!
rob_next = nums[n - 1]  # there's one house left, rob it
 
for i in range(n - 2, -1, -1):
    current = max(rob_next, rob_next_next + nums[i])
    rob_next_next = rob_next
    rob_next = current
 
return rob_next

An alternative code

t1 = 0  # max amt robbed up to the current house
t2 = 0  # max amt robbed up to before the current house
for current in nums:
    t1, t2 = max(current + t2, t1), t1
return t1

Think of t1 and t2 as two thieves

• t1 leaves a note of max amount that can be robbed up to this house
• t2 enters the house, communicate this info with t1 through walkie-talkie. At this time, t1 is at the next house
• The two thieves decide should they rob or not