House Robber

You'll turn a slow recursion into dynamic programming (DP) that remembers just two numbers. You need loops and recursion. Related chapter: dynamic programming.

1. The problem

Houses stand in a row, and each number is the money in one house (zero or more). Pick houses so that no two picked houses are next to each other, and return the largest total. You can skip any house. Don't change the input. This is LeetCode 198. Our function also returns 0 for an empty list.

[2,1,1,2] is the trap. Taking every other house gives 3 either way, but the best answer skips two houses in a row.

2. A correct baseline

def baseline(nums):
    def choose(i):
        if i>=len(nums): return 0
        return max(choose(i+1),nums[i]+choose(i+2))
    return choose(0)

assert baseline([2,7,9,3,1])==12
assert baseline([2,1,1,2])==4
assert baseline([0])==0

Each call branches into two more, so the number of calls grows exponentially, about 1.6 times with each extra house. With 40 houses, that's about 500 million calls. The recursion uses O(n) stack space.

The bottleneck. Different paths ask the same question again and again: "what's the best total from house i onward?" Taking house 0 and skipping house 1 both lead to asking about house 2.

3. The observation

Walk the houses left to right instead. At each house, you have two choices. Skip it, and keep the best total up to the previous house. Or take it: add its money to the best total up to two houses back, since the neighbor must be skipped. Pick the larger.

In [2,7,9]: up to the 7, the best is 7. At the 9, skipping keeps 7, and taking gives 2 + 9 = 11. So the best is 11. You only ever need the last two totals, not which houses you picked.

4. The solution and a trace

class Solution:
    def rob(self, nums: list[int]) -> int:
        """Nonnegative amounts along a line; adjacent houses cannot both be selected."""
        two_back=one_back=0
        for money in nums:
            current=max(one_back,two_back+money)
            two_back,one_back=one_back,current
        return one_back

solve=Solution().rob
assert solve([2,7,9,3,1])==12
assert solve([2,1,1,2])==4
assert solve([0])==0
assert solve([])==0

Trace [2,7,9,3,1]. The totals shown are from before each update:

5. Why it works

What stays true. Before each house, one_back is the best total up to the previous house, and two_back is the best total up to the house before that.

Why the update is right. Every valid pick either skips the current house or takes it. If it takes it, it must skip the neighbor. Those two cases cover every valid pick. The best of each case is one_back or two_back + money. Both are valid picks, so their maximum is the best total up to this house.

6. Cost, edge cases, and failure

Cost. One pass: O(n) time, growing in step with the number of houses. O(1) extra space, for the two totals.

Edge cases. An empty list returns 0. The line two_back, one_back = one_back, current reads both right-hand values before changing either. If you updated two_back first on its own line, you'd lose the value you need.

Where it fails. Taking every other house isn't enough:

nums=[2,1,1,2]
assert max(sum(nums[::2]),sum(nums[1::2]))==3
assert solve(nums)==4  # Counterexample to fixed-parity selection.

import random
rng=random.Random(198)
for _ in range(500):
    nums=[rng.randint(0,15) for _ in range(rng.randrange(13))]
    before=nums.copy()
    assert solve(nums)==baseline(nums)
    assert nums==before