House Robber Dynamic Programming: 5 Bold Wins You Must Know

House Robber is Climbing Stairs with attitude. Same DP skeleton, one adversarial twist.

Greedy fails here. Grabbing the richest house first loses on [5,1,1,5] — the two 5s aren't adjacent, but greedy adjacency repair still fumbles variants like [2,1,1,2]... you'll code it, feel clever, and fail hidden tests.

The fix is rob-or-skip per house: best(i) = max(nums[i] + best(i-2), best(i-1)). That's O(n) time, O(1) space with rolling variables. You'll derive it in a minute once you think in prefix optima. Let's build that reflex.

Maximise the Take Without Robbing Two Adjacent Houses

Given nums where nums[i] is cash in house i, rob a subset with no two adjacent for maximum total. Example [2,7,9,3,1] → 12 (houses 2 + 9 + 1: indices 0, 2, 4). Check: 2+9+1 = 12 beats 7+3 = 10 and 2+3+1 = 6.

Constraints: n to 100, values to 400. Small limits, but the pattern matters more than the size — circular (House Robber II) and tree (House Robber III) variants reuse this skeleton. Return a total, not the indices (track parents for indices — a standard extension).

Walk [2,7,9,3,1] by prefix optima: best(-1)=best(-2)=0. i=0: max(2+0, 0)=2. i=1: max(7+0, 2)=7. i=2: max(9+2, 7)=11. i=3: max(3+7, 11)=11. i=4: max(1+11, 11)=12. Answer 12. Each decision uses only solved prefixes.

Why Greedy Picks Wrong and Recursion Repeats the Work

Brute force: enumerate all 2^n subsets, keep valid max. O(2^n) time — dead past n = 25 (33M subsets). Correct, useless.

Greedy richest-first: pick the max house, delete its neighbors, repeat. It stumbles on streets like [1,100,1,1,100,1] where skipping a rich house unlocks better combinations, and repair-order variants fail unpredictably. No exchange argument exists — local riches don't compose under adjacency.

Interview play: 'Subsets are O(2^n) — dead. Greedy has no exchange proof under adjacency — I'll use prefix DP.' Two sentences that show you test strategies, not just remember them.

Rob or Skip: Every House Is a Two-Way Decision

Define best(i) = max haul from houses 0..i. Decide house i: rob it → nums[i] + best(i-2) (neighbor i-1 forbidden); skip it → best(i-1). Take the max: best(i) = max(nums[i] + best(i-2), best(i-1)), with best(-1) = best(-2) = 0.

Proof sketch by induction: bases hold (no houses → 0). Assume prefixes below i optimal. Any optimal i-solution either contains i (then its remainder is an optimal (i-2)-solution by cut-and-paste) or excludes i (then it's an optimal (i-1)-solution). The max of both cases is optimal. Each i computed once forward: O(n) time. Only i-1, i-2 are read → two rolling variables: O(1) space.

This is Climbing Stairs' skeleton with max replacing sum — same shape, adversarial operator. State that parallel live; interviewers reward family recognition.

The Rob-or-Skip Solution in Full Python

The code above is the complete LeetCode submission. Trace [2,7,9,3,1]: (0,0) → n=2: cur=2, (0,2) → n=7: cur=7, (2,7) → n=9: cur=11, (7,11) → n=3: cur=10→11, (11,11) → n=1: cur=12, (11,12). Returns 12. Trace []: loop skipped, returns 0. Trace [5]: cur=5, returns 5.

Complexity: O(n) time, O(1) space. No imports, no arrays, no recursion — safe at every limit.

class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2 = 0  # best up to i-2
        prev1 = 0  # best up to i-1
        for n in nums:
            cur = prev2 + n
            if prev1 > cur:
                cur = prev1
            prev2, prev1 = prev1, cur
        return prev1

One House, Two Houses and All-Zero Streets

Empty returns 0 (loop skipped). Single [5] returns 5. Two houses [2,1] returns 2 (rob richer). All-zeros returns 0. Alternating [5,1,1,5] returns 10 (both ends, non-adjacent). Large values need no special handling in Python (mention 32-bit int fit for Java/C++).

Shift-order trap: prev2, prev1 = prev1, cur must bind simultaneously (tuple assignment evaluates right-first). Sequential shifts (prev2 = prev1; prev1 = prev2 + n) reuse the new prev2 — trace [1,2,3,1] → must be 4, drifts to 5+ when shifted wrong.

Why Two Rolling Variables Replace the DP Array

Time O(n): one fold over houses, O(1) per step. Space O(1): two integers. Both meet lower bounds — every house must be considered (Ω(n) floor); only two prefix optima need memory (O(1) floor).

Whiteboard closer: 'Rob-or-skip per prefix, i-2 jump enforces adjacency, rolling pair compresses space.' Then bridge: 'Circle streets run this twice (exclude each end); tree streets lift rob/skip to post-order states.' Family mapped, round won.