House Robber

Interview Prep

Warm-upDynamic Programmingdprecurrence

The problem

A row of houses, each with some non-negative cash. You can rob any subset, but no two adjacent houses (an alarm triggers if both are robbed). Return the maximum amount obtainable. Equivalently: maximum-weight independent set on a path graph.

Pattern: linear DP, choose-or-skip

At each house, two choices: rob it (add its value, then jump two ahead) or skip it (move one ahead). Let f(i) = best achievable from index i onward. Then f(i) = max(f(i+1), nums[i] + f(i+2)). Base case f(n) = 0. The recurrence is the "Fibonacci with a choice" — the simplest non-trivial DP.

Equivalently, looking left-to-right: dp[i] = max take using houses 0..i, with recurrence dp[i] = max(dp[i−1], dp[i−2] + nums[i]). Since only the last two values are needed, the space collapses to O(1).

Memoized recursion

def rob_memo(nums: list[int]) -> int:
    cache = {}
    def helper(i):
        if i >= len(nums): return 0
        if i in cache: return cache[i]
        cache[i] = max(helper(i + 1), nums[i] + helper(i + 2))
        return cache[i]
    return helper(0)

Bottom-up DP

def rob_dp(nums: list[int]) -> int:
    n = len(nums)
    if n == 0: return 0
    dp = [0] * n
    dp[0] = nums[0]
    if n > 1: dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[n - 1]

Optimal: rolling pair

def rob(nums: list[int]) -> int:
    """O(1) space — only need the previous two states."""
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Trace

nums = [2, 7, 9, 3, 1]

prev2 = 0, prev1 = 0

i=0, x=2:  new = max(0, 0 + 2) = 2.   prev2=0,  prev1=2
i=1, x=7:  new = max(2, 0 + 7) = 7.   prev2=2,  prev1=7
i=2, x=9:  new = max(7, 2 + 9) = 11.  prev2=7,  prev1=11
i=3, x=3:  new = max(11, 7 + 3) = 11. prev2=11, prev1=11
i=4, x=1:  new = max(11, 11 + 1) = 12. prev2=11, prev1=12

return 12   (rob houses 0, 2, 4: 2 + 9 + 1 = 12)

Complexity

Variations worth knowing