House Robber: The Take or Skip Recurrence

This one is a Medium-rated classic reported from Google, Amazon, Adobe interviews: "House Robber". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Dynamic Programming pattern on sight. Part 3 of 11 in the Dynamic Programming arc.

The Problem

Houses on a street hold money; adjacent houses share an alarm, so you cannot rob two neighbors. Maximize the take. The archetype of choose-or-skip DP with a one-step exclusion constraint — and the base of a small franchise (circular street, binary tree).

Input:  nums = [2, 7, 9, 3, 1]
Output: 12
Rob houses 1, 3, 5: 2 + 9 + 1.

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

At each house: rob it (adding to the best two back) or skip it (best one back). Whenever a constraint reaches exactly one step behind, the state 'best using the first i items' with a two-case max is the shape — and only two previous values stay live.

The Approach

best_i = max(best_(i−1), best_(i−2) + nums[i]), bases for zero and one houses, rolled into two variables. Fifteen seconds of code after ninety seconds of setup — the correct time allocation on any DP question.

The classic slip is greedy alternation (rob every other house) — [2, 1, 1, 2] breaks it, robbing both ends. Keep that counterexample loaded.

Python Solution

def rob(nums: list[int]) -> int:
    """Max non-adjacent sum."""
    prev2, prev1 = 0, 0                # best through i-2, i-1
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Complexity

• Time: O(n) — one decision per house
• Space: O(1) — two rolling values

Interview Tips and Follow-Ups

• House Robber II (circular street): run this twice — excluding the first house, then the last — and take the max. Ten-second answer if prepared.
• House Robber III (houses on a binary tree) returns a (rob, skip) pair per subtree — DP composed with the DFS arc's post-order shape.
• Use [2, 1, 1, 2] to kill the greedy in one breath when asked 'why not alternate?' — counterexamples end debates faster than proofs.

More Dynamic Programming problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.