House Robber

House Robber is the first DP problem most interviewers reach for. It has one index, two choices per step, and a rule that fits on one line — but a greedy guess gets it wrong, so you have to think in states.

It is also the best problem for practising all four stages, because every stage is short enough to write in a minute.

The problem

A row of houses each holds some money, given as a list of non-negative integers. You may take the money from any houses you like, except that you may never take from two neighbouring houses. Return the largest total you can take.

• [2, 7, 9, 3, 1] → 12. Take houses 0, 2 and 4: 2 + 9 + 1.
• [5, 1, 1, 5] → 10. Take the two ends: 5 + 5.

Constraints: 1 ≤ n ≤ 100, 0 ≤ money ≤ 400.

Clarifying questions

• Can amounts be zero? Yes. Negative? No.
• Return the total or the houses? The total. Returning the houses is a follow-up.
• Is the street a line or a circle? A line. The circle is a follow-up.

Approach 1: the simple way — try every allowed set

Each house is take or skip, so there are 2ⁿ sets; keep the ones with no two neighbours and take the best sum. The recursive version of the same search: from house i, either skip it and go on from i + 1, or take it and jump to i + 2.

1def rob_rec(nums: list[int]) -> int:2    """best(i) = most money from houses i .. n-1."""3    def best(i: int) -> int:4        if i >= len(nums):5            return 06        return max(best(i + 1), nums[i] + best(i + 2))   # skip i, or take i7    return best(0)

Why it is too slow. Each call makes two more, so the work grows like the Fibonacci numbers: 35,421 calls for n = 20 and 4,356,617 for n = 30. For n = 100 it would make about 7 × 10²⁰ calls — over a million years of work. Yet there are only n + 2 different questions — best(0) to best(n + 1) — so almost all those calls repeat each other.

Two greedy ideas fail too. "Take every other house" gives 5 + 1 = 6 on [5, 1, 1, 5], not 10. "Take the richest house first" can block two houses that together beat it.

The key insight

Stand at house i and look back. The best total for the first i houses depends only on two earlier answers:

• Skip house i → you keep the best for the first i − 1 houses.
• Take house i → you cannot have taken house i − 1, so you add its money to the best for the first i − 2 houses.

The state is dp[i] = the most money from the first i houses. The transition is dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]). How you reached dp[i - 2] does not matter — only its value — which is exactly the optimal substructure DP needs.

Approach 2: memoisation

1from functools import cache23def rob_memo(nums: list[int]) -> int:4    @cache5    def best(i: int) -> int:6        if i >= len(nums):7            return 08        return max(best(i + 1), nums[i] + best(i + 2))9    return best(0)

Identical logic plus a cache: each best(i) is computed once. O(n) time, O(n) space for the cache and the stack.

Approach 3: tabulation

1def rob_table(nums: list[int]) -> int:2    """dp[i] = most money from the first i houses."""3    n = len(nums)4    dp = [0] * (n + 1)                   # dp[0] = 0: no houses, no money5    dp[1] = nums[0]                      # one house: take it6    for i in range(2, n + 1):7        dp[i] = max(dp[i - 1],                  # skip house i-18                    dp[i - 2] + nums[i - 1])    # take it9    return dp[n]

The table is one longer than the street so that dp[0] can mean "no houses". On [2, 7, 9, 3, 1] it fills as [0, 2, 7, 11, 11, 12].

Approach 4: two variables

The transition reads only the previous two entries, so keep just those.

1def rob(nums: list[int]) -> int:2    """Most money from non-adjacent houses, O(1) extra space."""3    prev2, prev1 = 0, 0                  # best for the first i-2 and i-1 houses4    for money in nums:5        prev2, prev1 = prev1, max(prev1, prev2 + money)6    return prev1

Dry run on [2, 7, 9, 3, 1]:

Answer 12. House 3 was skipped even though 3 is more than 1, because taking it would block house 4 and force skipping house 2's 9. The table weighs both options at every step, which a greedy rule cannot.

Complexity: O(n) time — one pass, O(1) work per house. O(1) extra space.

Edge cases

• One house — the loop runs once and returns its money. (The table version needs dp[1] = nums[0], which is why n ≥ 1 matters there.)
• Two houses — the answer is the larger one; the loop handles it with no special case.
• All zeros — returns 0.
• Very large n — the recursion versions hit Python's recursion limit around n = 1,000; the loop does not.

Follow-ups

• Houses in a circle (House Robber II) — the first and last houses are now neighbours, so at least one of them is left out. Run the straight-line solver twice, on nums[1:] and on nums[:-1], and take the larger. On [2, 7, 9, 3, 1] that gives 11 instead of 12. Check len(nums) == 1 first.
• Which houses? — keep the full table, then walk back from the end: if dp[i] == dp[i - 1], house i − 1 was skipped; otherwise it was taken, so jump to i − 2.
• Houses on a binary tree (House Robber III) — return a pair from each node, (best if this node is taken, best if skipped), and combine the children's pairs on the way up.