Lab 01 — 1D DP Foundations (House Robber)

Goal

Implement House Robber (LC 198) four times — brute recursion, memoized, tabulated, and space-optimized — to internalize the brute → memo → tabulated → space-optimized progression that this entire phase is built around. After this lab you should be able to recognize a 1D DP problem in <60 seconds, derive the state and recurrence in <90 seconds, and produce the O(1)-space final solution from a blank screen in under 5 minutes.

Background Concepts

A 1D DP has state dp[i] indexed by a single integer — the prefix length, the position, or the day. The recurrence reads only O(1) previous values, which is what makes the rolling-array (O(1)-space) trick work. House Robber is the canonical example because it has exactly two choices per state (rob this house or skip), each of which determines the next state cleanly. The recursive formulation f(i) = max(f(i-1), f(i-2) + house[i-1]) reads two previous values; the tabulated version is a direct loop; the space-optimized version keeps two scalars.

The four-stage progression is the discipline of this lab. Don’t skip stages. The interviewer at staff level routinely asks “show me the recursive version first” specifically to test whether you can derive the recurrence from a brute force. Candidates who memorized the iterative solution but never wrote the recursion fail this question.

Interview Context

House Robber is a top-30 phone-screen DP problem at Amazon, Google, Microsoft, and Meta. Its variants — House Robber II (circular), House Robber III (tree, see Lab 08) — extend it. Bombing this problem on a phone screen is a near-instant rejection at L4. The reason: it has the simplest possible state (a single integer) and the simplest possible recurrence (two-way choice). If you can’t do this one, you can’t do any DP.

Problem Statement

You are a robber planning to rob houses arranged in a line. Each house has a non-negative integer amount of cash, given by nums[i]. You cannot rob two adjacent houses (the alarm system links them). Return the maximum amount of cash you can rob.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 400

Clarifying Questions

Are amounts non-negative? (Yes — given.)
Can nums be empty? (No, length ≥ 1 by constraint, but always confirm.)
Are houses arranged in a line or a circle? (Line for LC 198; LC 213 is the circular variant.)
Can two adjacent houses both be skipped? (Yes — skipping is always allowed.)
Must we rob at least one house? (No — robbing nothing is allowed if all values are 0; in practice, since amounts are non-negative, the optimum is always ≥ 0.)

Examples

nums = [1, 2, 3, 1]            → 4   (rob houses 0 and 2: 1 + 3)
nums = [2, 7, 9, 3, 1]         → 12  (rob houses 0, 2, 4: 2 + 9 + 1)
nums = [2, 1, 1, 2]            → 4   (rob houses 0 and 3: 2 + 2)
nums = [5]                     → 5
nums = [0, 0, 0]               → 0

Initial Brute Force

At each house, two choices: rob it (and skip the next) or skip it. Recursively try both:

def rob_brute(nums):
    def f(i):
        if i >= len(nums):
            return 0
        return max(f(i + 1), nums[i] + f(i + 2))
    return f(0)

Brute Force Complexity

Each call branches into 2 recursive calls, so we visit O(2^N) subproblems. At N=100, that’s 2^100 = 1.27 × 10^30 — far beyond any time limit. Space is O(N) for the recursion stack.

Optimization Path

The brute force is exponential because the same f(i) is recomputed exponentially many times. There are only N+1 distinct values of i, so memoization collapses the work to O(N). From there, tabulation removes the recursion overhead. Finally, since the recurrence reads only dp[i-1] and dp[i-2], we keep two scalars instead of the full array — O(1) space.

Each stage strictly improves on the previous: brute → memo (cache; from O(2^N) to O(N) time), memo → tabulated (loop instead of recursion; same complexity, no stack overhead), tabulated → space-optimized (drop the array; from O(N) to O(1) space).

Final Expected Approach

Define dp[i] = maximum cash robbed from the first i houses. Recurrence:

dp[0] = 0                                         (no houses to rob)
dp[1] = nums[0]                                   (one house — rob it)
dp[i] = max(dp[i-1],          # skip house i-1
            dp[i-2] + nums[i-1])  # rob house i-1

Answer: dp[N]. Since the recurrence reads only dp[i-1] and dp[i-2], keep two scalars: prev2 and prev1.

Data Structures Used

A 1D array dp of size N+1 (tabulated).
Two scalars prev2, prev1 (space-optimized).
For brute / memo: function call stack and a memoization dict / lru_cache.

Correctness Argument

By induction on i. Base: dp[0] = 0 (correct — no houses). dp[1] = nums[0] (correct — one house, rob it). Inductive step: at step i, the optimal robbery either does or does not rob house i-1. If it does, the remaining is the optimal over the first i-2 houses (since we can’t rob i-1’s neighbors), giving dp[i-2] + nums[i-1]. If it does not, the remaining is the optimal over the first i-1 houses, giving dp[i-1]. Taking the max covers both cases — this exhausts the choice space, so the recurrence is correct.

Complexity

Stage	Time	Space
Brute force	O(2^N)	O(N) (stack)
Memoized	O(N)	O(N) (cache + stack)
Tabulated	O(N)	O(N)
Space-optimized	O(N)	O(1)

Implementation Requirements

All four stages are required.

# ---- Stage 1: Brute force ----
def rob_brute(nums):
    def f(i):
        if i >= len(nums):
            return 0
        return max(f(i + 1), nums[i] + f(i + 2))
    return f(0)

# ---- Stage 2: Memoized ----
from functools import lru_cache
def rob_memo(nums):
    @lru_cache(None)
    def f(i):
        if i >= len(nums):
            return 0
        return max(f(i + 1), nums[i] + f(i + 2))
    return f(0)

# ---- Stage 3: Tabulated ----
def rob_tab(nums):
    n = len(nums)
    if n == 0: return 0
    dp = [0] * (n + 1)
    dp[1] = nums[0]
    for i in range(2, n + 1):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
    return dp[n]

# ---- Stage 4: Space-optimized ----
def rob(nums):
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Tests

[] → 0 (defensive, even if constraint disallows).
[5] → 5.
[5, 1] → 5.
[1, 2, 3, 1] → 4.
[2, 7, 9, 3, 1] → 12.
[0, 0, 0, 0] → 0.
[400, 400, 400] → 800 (rob ends).
All four implementations should produce identical results — write a randomized stress comparator on nums of length 1..15 and check rob_brute == rob == rob_tab == rob_memo.

Follow-up Questions

“What if houses are in a circle?” (LC 213 — House Robber II) → Run the line algorithm twice: once excluding house 0, once excluding house N-1; take the max.
“What if houses are nodes of a binary tree?” (LC 337 — House Robber III) → Tree DP with (rob, skip) tuple per node. See Lab 08.
“Reconstruct which houses were robbed.” → Track back-pointers in tabulated version, or re-derive by walking dp backwards: at each i, robbed iff dp[i] > dp[i-1].
“What if the no-rob constraint extends to k-apart instead of adjacent?” → dp[i] = max(dp[i-1], dp[i-k-1] + nums[i-1]).
“What if amounts can be negative?” → Same recurrence; dp[i-2] + nums[i-1] may be less than dp[i-1], so the max correctly drops it.

Product Extension

Variations of this problem appear in real systems: scheduling non-conflicting jobs (interval scheduling with profit), selecting non-overlapping ad slots, and assigning tasks to time-slots with cooldown. The 1D DP framework generalizes when “no two adjacent” becomes “no two within window K” or “must wait at least T”.

Language/Runtime Follow-ups

Python: lru_cache makes memoization a one-line addition. At N>1000, default recursion limit overflows — bump with sys.setrecursionlimit(10**6) or use the tabulated version. The space-optimized version is idiomatic and fast.
Java: use int[] dp for tabulated; Arrays.fill(dp, -1) + recursion for memoization. Java’s default stack is ~512KB; recursion overflows around N=10000.
Go: tabulated is idiomatic; Go has no lru_cache so memoization needs a manual map[int]int or []int.
C++: tabulated with vector<int>; memoization with a vector<int> memo(N, -1) and a recursive helper.
JS/TS: same idiom as Python but no lru_cache — use Map for memoization.

Common Bugs

Returning dp[N-1] instead of dp[N] (or vice versa) — depends on whether dp[i] indexes “first i houses” or “ending at i”. Pick one convention and stick to it.
Initializing dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]) — works, but only if you handle N=1 separately. The cleaner convention is dp[0]=0, dp[1]=nums[0].
Off-by-one in dp[i-2] + nums[i-1] vs dp[i-2] + nums[i-2] — depends on the index convention. Verify on [5].
Forgetting that nums can be empty — guard with if not nums: return 0 even though constraints say N ≥ 1.
Space-optimized version: swapping prev2, prev1 = prev1, max(prev1, prev2 + x) in the wrong order. Tuple-assignment in Python evaluates the RHS first, so this is correct; in Java/C++ you need an explicit temp.

Debugging Strategy

When the answer is wrong by a small amount: print the entire dp array for nums = [2, 7, 9, 3, 1] (expected dp = [0, 2, 7, 11, 11, 12]). If it differs, trace the iteration step where dp first deviates and inspect the recurrence at that index. When the answer is wildly wrong (negative, or much smaller): suspect index off-by-one or an if condition that’s flipped. When TLE: confirm you’re not running the brute force.

Mastery Criteria

Recognized House Robber as a 1D DP problem within 60 seconds.
Wrote the brute recursive formulation in <2 minutes from cold start.
Added @lru_cache to produce the memoized version in <30 seconds.
Wrote the tabulated version in <3 minutes from blank screen, passing all five test cases first try.
Wrote the space-optimized version in <2 minutes after the tabulated.
Stated O(N) time and O(1) space unprompted.
Articulated the inductive correctness argument in <30 seconds.
Solved LC 198 unaided in <8 minutes total (all four stages).
Solved LC 213 (House Robber II) unaided in <12 minutes by running the line algorithm twice.

LeetCode Interview — Extreme Coding