House Robber

Difficulty: Medium

Problem

Along a street, house i holds nums[i] worth of loot. Neighboring houses are wired to the same alarm, so breaking into two adjacent ones brings the police. Pick the houses to rob so that no two picked houses are next to each other and the total is as large as possible. DP Foundations concept 7 previewed this exact street; now you build the full arc yourself, your first DECISION DP.

Example

Input: nums = [5,3,4,11,2]
Output: 16
Explanation: Rob houses 0 and 3: 5 + 11 = 16. They are not adjacent, and nothing legal beats it; for example 5 + 4 + 2 = 11 is much smaller.

Brute-force approach

The naive try-everything recursion is Step 1 of the guided walkthrough: this lesson walks the full arc from O(2^n) recursion to the O(1)-space table in one place.

Optimal approach

Key insight: At every house one question: rob it (plus the best two back) or skip it (best one back). The table answers it n times and the street is solved.

Classic 1D decision DP: at each house take max(skip, rob) using the best answers one and two houses back, filled left to right, then rolled into two variables for O(1) space.

Steps

STATE: dp[i] = max loot from houses 0..i, whether or not house i is robbed
TRANSITION: dp[i] = max(dp[i−1], dp[i−2] + nums[i]), skip vs rob
BASE: an empty street is worth 0, so start prev2 = prev1 = 0
Fill left to right. Each house costs one max() call
Only two lookbacks are ever alive → roll them in two variables for O(1) space

Time complexity: O(n) · Space complexity: O(1) with rolling variables

Pseudocode

function rob(nums):
    prev2 = 0                 // best loot from zero houses
    prev1 = 0                 // ditto: no special cases needed
    
    for each loot x in nums:
        cur = max(____,       // skip this house
                  ____)       // rob this house
        prev2 = ____          // roll: yesterday slides back
        prev1 = ____          // roll: today becomes yesterday
    
    return ____

Hints

Skipping house x means the plan doesn't change at all. Which variable already holds the best through the PREVIOUS house?
Robbing house x pockets its loot on top of the best plan that leaves the neighbor alone. The answer from TWO houses back.
The roll slides the window: two-back takes yesterday's value FIRST, then yesterday takes today's cur. Swap the order and you copy cur into both.
When the loop ends, the freshest 'best through the last house' IS the whole street's answer, which variable holds it?

Complexity questions

The Step-1 recursion with no memo, what is its time complexity?

O(2ⁿ): every call branches into skip and rob, and the same prefixes get re-solved in both subtrees. rob(i) spawns rob(i−1) and rob(i−2), each spawning two more. A call tree that roughly doubles per level. Because rob(i−2) is recomputed inside both branches, the work is exponential: the same explosion as naive Fibonacci, with max instead of +.

With the memo or the table, what does the time drop to?

O(n): only n distinct subproblems exist, each solved once with an O(1) max. There are only n + 1 distinct questions, 'best loot through house i', and DP answers each exactly once. Each answer costs one comparison and one addition. Five houses, five max() calls; a million houses, a million.

Why can the full dp array shrink to O(1) space for House Robber?

The transition reads only dp[i−1] and dp[i−2]. Once a cell is three slots old it's never touched again, so two rolling variables suffice. Look at the transition's diet: exactly two lookbacks, every time. Anything older is dead weight, so prev1 and prev2 carry the entire live window and the roll slides it one house right each turn. Contrast with a transition that reads ALL earlier cells (like Longest Increasing Subsequence), that one can't roll.

New street: [2,1,1,2]. What do greedy strategies answer, and what does DP answer?

Greedy variants get 3, but DP finds 4: rob BOTH 2s, calmly skipping two houses in a row. Walk it. Eager left-to-right robbing: take 2, skip house 1, take house 2's 1, and now the final 2 is blocked: total 3. Strict alternation: 2+1 = 3 or 1+2 = 3. DP fills [2, 2, 3, 4]: dp[3] = max(dp[2], dp[1] + 2) = max(3, 4) = 4, robbing houses 0 and 3 and skipping TWO middle houses in a row. Memorize this street: it's the counterexample that kills 'alternate' intuition on sight.

Check your understanding of House Robber

You may rob any subset of houses you like. What exactly makes a subset ILLEGAL?

Robbing two houses that are directly next to each other. The ONLY rule is no two ADJACENT robbed houses. You may rob none, one, or nearly all of them, and you may skip two, three, or ten houses in a row, in [2,1,1,2] the optimal plan skips BOTH middle houses. 'Alternate strictly' is a stronger, wrong rule that this lesson will explicitly demolish.

Why can't a greedy rule like 'walk the street and grab whichever house looks richest right now' be trusted?

Choices INTERACT: in [2,7,9,3,1], grabbing the gleaming 7 forfeits the 9 next door and caps you at 7+3 = 10, while the patient plan 2+9+1 = 12 wins. Walk it: next to a humble 2, the 7 looks like the obvious grab, but robbing it arms the alarms on houses 0 AND 2, silently disqualifying the street's biggest prize, the 9. Best finish from there: 7 + 3 = 10. The optimal thief takes the 2 precisely so the 9 stays available: 2 + 9 + 1 = 12. When one choice constrains the next, local best is not global best, that interaction is DP's cue.

Which sentence is the PRECISE meaning of dp[i]?

dp[i] = the max loot obtainable from houses 0..i, whether or not house i itself is robbed. Precision matters: dp[i] covers BOTH kinds of plans. Those that rob house i and those that skip it. That's exactly what lets dp[i−1] serve as the complete 'skip house i' answer later. Define dp[i] as 'house i robbed' only, and the clean one-line transition falls apart.

Standing at house i with dp[i−1] and dp[i−2] already known, what is the transition?

dp[i] = max(dp[i−1], dp[i−2] + nums[i]). Skip house i, or rob it on top of the best from two back. Case-split on the LAST decision. SKIP house i → your plan is exactly the best for houses 0..i−1, which is dp[i−1]. ROB house i → pocket nums[i], and the rest of the plan must leave house i−1 alone, so add the best for 0..i−2: dp[i−2] + nums[i]. Two legal futures, take the max. (dp[i−1] + dp[i−2] is Climbing Stairs' SUM, counting problems add ways, decision problems max values.)

When we ROB house i, why is dp[i−2] the right partner to add, why not dp[i−1]?

Robbing house i puts house i−1 off-limits, so the best COMPATIBLE past is everything through house i−2, and dp[i−2] already holds that, optimally. dp[i−1] might have robbed house i−1: stack nums[i] on top and the alarm trips. dp[i−2] is guaranteed compatible: nothing in houses 0..i−2 can be adjacent to house i. And note what it does NOT say: dp[i−2] doesn't force robbing house i−2. It quietly includes skip-heavy plans too, which is exactly how [2,1,1,2] gets to rob both ends.