House thief

House Thief is a 1-D decision-DP: at each house you make a binary choice (rob it or skip it), and that choice locks out the previous house, so the optimal value at house i can only be built from the optimal values at houses i-1 and i-2 — no other history matters.

Recognize the pattern

• Items in a line, each with a value, and a rule that adjacent items are mutually exclusive ("can't pick two in a row", "no two consecutive days/seats/houses").
• You want a max/min over a sequence subject to a local exclusion constraint — not a global budget (that's knapsack).
• The decision at position i depends only on a fixed, small window of previous decisions (here: 2) — a strong signal for an O(1)-space rolling DP.

Brute force → optimal

Brute force: recursively branch at each house into "rob" and "skip" regardless of what was chosen before, then filter to keep only the subsets that never pick two adjacent houses, and take the max valid sum. Because every house spawns two branches with no pruning, the recursion tree has exactly 2 branches per level for n levels. Cost: O(2ⁿ) time, O(n) stack space.

Optimal (DP): let dp[i] = max money stealable from the first i houses (1-indexed, value w[i]). At house i you either skip it (dp[i-1]) or rob it and add to the best achievable two houses back (dp[i-2] + w[i]), since robbing i forbids i-1.

dp[0] = 0
dp[1] = w[1]
dp[i] = max(dp[i-1], dp[i-2] + w[i])   for i >= 2
answer = dp[n]

Cost: O(n) time, O(1) space — only the last two dp values are ever read.

Complexity, derived

Time: the recurrence dp[i] = max(dp[i-1], dp[i-2]+w[i]) does exactly one comparison and one addition per index, once each, for i = 2..n → n-1 constant-work steps → O(n). Contrast the brute-force recursion described above: branching into "rob" and "skip" at every house with no pruning gives T(n) = 2·T(n-1) + O(1), which unrolls to O(2ⁿ) — the same exponential bound stated in the previous section, now derived from the recurrence rather than just the branching count. The DP is not a tighter analysis of this same recursion; it is a different formulation that recognizes only n distinct subproblems exist (one per house) instead of 2ⁿ candidate subsets, so computing each subproblem once collapses the cost to O(n).

Space: a full table costs O(n); since dp[i] only ever reads dp[i-1] and dp[i-2], two rolling variables suffice → O(1) auxiliary space.

Worked example

Input: [2, 5, 1, 3, 6, 2, 4] (indices 1..7)

dp[7] = 15, matching the expected output (5 + 6 + 4). Backtracking the choices that produced each max recovers the actual houses picked.

Java (O(1) space)

class HouseThief {
    static int maxSteal(int[] w) {
        int prev2 = 0, prev1 = 0;
        for (int x : w) {
            int cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Pitfalls

• Off-by-one in the base cases: forgetting dp[0]=0 or mishandling n=1 (must return w[0], not 0) causes silent underflow on small inputs.
• Confusing this with knapsack: House Thief has no capacity/weight budget, only an adjacency exclusion — using a 2-D weight table is unnecessary overhead.
• Circular variant ("House Thief II", houses in a circle so house 1 and house n are adjacent): naively running the linear DP over all n houses ignores the wrap-around constraint and overcounts. Fix: run the linear DP twice, once excluding house 1 and once excluding house n, take the max.
• Trying to reconstruct the chosen houses without storing choice history (or the dp array) — O(1)-space rolling variables can compute the value but not the path unless you also keep parent pointers or replay the table.

When to use / when NOT

Use this linear DP whenever the constraint is "no two adjacent picks" over a sequence — house robbery, max sum of non-adjacent array elements, scheduling non-overlapping same-length slots on a line.

Don't use it when the exclusion is not just "adjacent" but a general interval-overlap or a weight/capacity budget — that's Weighted Interval Scheduling (sort by end time, binary-search the last compatible interval, dp[i] = max(dp[i-1], value[i] + dp[p(i)])) or 0/1 Knapsack respectively. Those handle richer constraints at the cost of O(n log n) or O(n·W) instead of O(n).

Trade-off vs brute force: DP trades the exponential 2ⁿ exploration for O(n) time by exploiting overlapping subproblems and optimal substructure; the price is that you must trust the recurrence captures every relevant case (it does here, because the only interaction between choices is immediate adjacency).

Takeaways

• House Thief is the canonical "no two adjacent" 1-D DP: dp[i] = max(dp[i-1], dp[i-2]+w[i]).
• The O(2ⁿ) brute-force recursion (branch into rob/skip at every house, filter invalid subsets) collapses to O(n) once you notice there are only n distinct subproblems — one per house — instead of 2ⁿ candidate subsets to enumerate.
• Only the last two states matter, so space drops from O(n) to O(1) — always ask "how far back does the recurrence look?" to size your rolling window.
• Recognize the family: interval scheduling and knapsack generalize this same shape when the exclusion rule gets richer.

Recall: Why does House Thief need to look back only 2 states instead of keeping the full dp array, and under what change to the problem (e.g., can't rob 2 houses within any 3 consecutive) would that window need to grow?

Synthesized from classic "House Robber" DP formulations (e.g., LeetCode 198/213) and standard interval-scheduling/knapsack DP references for the trade-off comparison.