“Know how to solve every problem that has been solved.”“What I cannot create, I do not understand.”— Richard Feynman
House Robber
Interview Prep
Warm-upDynamic Programmingdprecurrence
The problem
A row of houses, each with some non-negative cash. You can rob any
subset, but no two adjacent houses (an alarm triggers if both are
robbed). Return the maximum amount obtainable. Equivalently:
maximum-weight independent set on a path graph.
Pattern: linear DP, choose-or-skip
At each house, two choices: rob it (add its value, then jump two
ahead) or skip it (move one ahead). Let f(i) = best
achievable from index i onward. Then
f(i) = max(f(i+1), nums[i] + f(i+2)). Base case
f(n) = 0. The recurrence is the "Fibonacci with a
choice" — the simplest non-trivial DP.
Equivalently, looking left-to-right: dp[i] = max take
using houses 0..i, with recurrence
dp[i] = max(dp[i−1], dp[i−2] + nums[i]). Since only
the last two values are needed, the space collapses to
O(1).
Memoized recursion
def rob_memo(nums: list[int]) -> int: cache = {} def helper(i): if i >= len(nums): return 0 if i in cache: return cache[i] cache[i] = max(helper(i + 1), nums[i] + helper(i + 2)) return cache[i] return helper(0)
Bottom-up DP
def rob_dp(nums: list[int]) -> int: n = len(nums) if n == 0: return 0 dp = [0] * n dp[0] = nums[0] if n > 1: dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) return dp[n - 1]
Optimal: rolling pair
def rob(nums: list[int]) -> int: """O(1) space — only need the previous two states.""" prev2 = prev1 = 0 for x in nums: prev2, prev1 = prev1, max(prev1, prev2 + x) return prev1
Under the Hood
The same way a mechanic opens the hood and points at the radiator, the
alternator, the timing belt — here is an annotated tour of what's
actually going on in the working code or math above. No questions, no
reveals. Just labels on the parts.
prev2 = prev1 = 0
The initialization. Both variables start at zero, encoding the rule
"robbing no houses scores 0." This is what makes the loop's very
first iteration produce the right answer: when the algorithm meets
the first house and asks "skip (carry forward prev1 = 0)
or rob (gain x + prev2 = x + 0)?", both options are
computed correctly because prev2 faithfully represents
"best score using houses two-or-more ago" — and there weren't any.
for x in nums
The loop iterates over house values, not indices. The
algorithm never tracks which houses were chosen; it only carries
forward running maxima. To recover the actual set of robbed houses
you'd need to record the per-step rob-vs-skip decision and walk
backward through them — the reconstruction probe in Try First spells
that out.
prev2, prev1 = prev1, max(prev1, prev2 + x)
The rolling update. Done as a single tuple assignment so the new
values are computed from the old ones before any of them
get overwritten — that's Python evaluating the entire right-hand
side first. Written as separate statements, you'd need a temporary
variable. The advancement: prev1 moves forward to hold
the new "best on the prefix including this house," and
prev2 inherits what prev1 just was — i.e.,
"best on the prefix NOT including this house."
max(prev1, prev2 + x)
The actual choice. prev1 is "best score if we skip this
house"; prev2 + x is "best score if we rob this house"
— and the use of prev2 (not prev1) is what
enforces the no-adjacent constraint, because robbing this house is
only allowed when the previous one was skipped. The max
picks the better option silently, without ever recording which one.
return prev1
The final answer is the maximum loot achievable. By construction,
prev1 at termination holds the answer on the full
array. Note the function returns ONLY the total — not the houses
involved. Reconstructing the actual subset requires extra
bookkeeping (recorded decisions, plus a backward walk).
Each prompt asks a checkable question about the working code or math
above — predict an output, derive a sign, state an invariant, find a
bug. Commit to an answer before clicking "reveal." That commitment is
the whole point: if your answer matched, you understand the piece you
were looking at; if it didn't, that's the part worth re-reading.
invariant
Pause the rolling-pair version at the top of iteration i, before
the update fires. State precisely what prev1 and prev2
hold in terms of the original problem applied to a prefix of nums.
Be specific about which prefix.
answer
At the top of iteration i:
prev1 = the answer to House Robber on the prefix nums[0:i] (the first i houses).
prev2 = the answer to House Robber on the prefix nums[0:i−1] (the first i−1 houses).
After the update line runs, prev1 advances to hold the answer on nums[0:i+1], and prev2 shifts to what prev1 just was. The whole algorithm is a two-step sliding window over the sequence of answers A(0), A(1), A(2), …, A(n), where A(k) is the House Robber answer for the first k houses. The recurrence A(k) = max(A(k−1), A(k−2) + nums[k−1]) is just Fibonacci with a choice rule — the simplest non-trivial DP, and an example of why "what does this variable mean" is the most important question you can ask of any DP.
predict
Predict rob([5, 5, 5, 5, 5, 5, 5, 5, 5, 5]) — ten houses, each
worth 5 — without running the code. Then state the closed form for
rob([c]·n) (an array of n copies of a constant
c > 0).
hint
Don't simulate the loop. Reason about which subsets of indices are
even legal under the no-adjacent constraint, then figure out the
largest one.
answer
For ten 5s, the answer is 25. You can rob houses
{0, 2, 4, 6, 8} for 25, and you can't fit a sixth
non-adjacent house in a row of ten.
Closed form: rob([c]·n) = c · ⌈n/2⌉. The maximum
independent set on a path of n vertices has size
⌈n/2⌉, and on a constant-weight array each house in that
set contributes c. The ceiling is doing real work — try
odd n versus even n and notice that the
"spare" house on the end gets picked up for free.
why does this work
Run the memoized version rob_memo on an array of n
distinct houses. How many entries does the cache dict end up
with? The recurrence at each node makes two recursive calls — and
2^n would be plausible. Why isn't it that?
answer
Exactly n entries: one for each call helper(0)
through helper(n−1). The calls helper(n) and
helper(n+1) hit the base case i >= len(nums)
and return before touching the cache.
The reason it isn't 2^n is the entire point of dynamic
programming. Each helper(i) is determined entirely by
i — there's no "which branches did I take to get here"
state. So the recursion tree has at most n distinct
subproblems, and memoization collapses the exponential call tree onto
them. This is the "overlapping subproblems" property: not a property of
the algorithm, a property of the problem itself. House Robber has it.
SAT and Graph Coloring don't — which is why they don't have
polynomial-time DPs.
find the bug
Replace prev2 + x with 0 + x in the rolling-pair
version. The code still runs, still returns a number. prev2
is now dead code, but ignore that — what problem does the modified code
correctly solve? It is the correct algorithm for something.
answer
The recurrence becomes prev1 = max(prev1, x). That's the
running maximum: starting from 0, take the larger of the
current running max and the new element. After the loop,
prev1 = max(0, max(nums)).
So the "House Robber with the broken recurrence" is exactly
maximum single element, or zero if all values are negative. A
real algorithm — just for a different problem. This is a useful
diagnostic habit: when you mutate a recurrence and want to know what
you've actually built, simplify it and see which classical algorithm
falls out. Sometimes the answer is "nothing useful." Here, it's a
familiar one in disguise.
trace
rob([3, 1, 1, 3]) returns 6 — but the function
never tells you which houses that 6 came from. Extend the
rolling-pair version to also return the list of indices robbed in some
optimal solution. Then explain why this required more care than you
might have expected.
hint
You can't reconstruct the path from prev1 and
prev2 alone — they only hold scalars. You need to record,
at each step, whether the update took the "skip" branch or the "rob"
branch.
answer
Key idea: at each step, record whether the rob-branch or the
skip-branch won — a single boolean per index. After the loop, walk
those booleans backward: at index i, if you
robbed, jump to i−2; if you skipped, go to
i−1. On [3, 1, 1, 3] the walk produces
[0, 3] — rob houses 0 and 3 for 3 + 3 = 6.
The subtlety is that decision[i] doesn't directly tell you
which subset is optimal — it tells you the local better-of-two at step
i. The actual subset emerges from threading those local
choices into a coherent backward walk. This back-pointer pattern is
universal across DP: the scalar answer is cheap; reconstructing the
witness costs an extra pass and a per-step record of the decision.
Almost every DP interview question has a follow-up of "now print the
actual answer" — so worth internalizing rather than re-deriving on
the spot.
Hack This
The code above works. Don't reinvent it — pull it into an editor, run it, and
try the modifications below. Each one is small. Each one will change the behavior
in a specific way; the question is which way.
trivial
The page opens by calling House Robber "Fibonacci with a choice." Make
that statement literal: in the rolling-pair version, replace
max(prev1, prev2 + x) with prev1 + prev2, and
change the initialization from prev2 = prev1 = 0 to
prev2, prev1 = 0, 1. Now run it on an array of length 20
— the values in nums are irrelevant since you've stopped
reading them. What do you get back, and what's the relationship between
it and nums?
hint
You should be looking at F(21) = 10946. The two-line
recurrence with + in place of max is the
exact Fibonacci recurrence; you've physically deleted the "choice"
half of "Fibonacci with a choice" and what's left is Fibonacci itself.
Worth asking what else changes if you swap max for
min, for AND, for product — same DAG, same
recurrence shape, totally different problems. (Semiring DP, if you
want to chase that thread.)
trivial
In the rolling-pair version, change prev2 + x to
prev1 + x. You've quietly deleted the no-adjacent
constraint — every house is now allowed to be robbed regardless of its
neighbors. Run it. What does the algorithm now compute? Then answer the
deeper question: where exactly, in the original code, did the adjacency
constraint live?
hint
The constraint never appears as an if. It's encoded
entirely in which previous state the recurrence reaches back
to. prev2 versus prev1 is the constraint.
small
Replace the recurrence with the multiplicative analogue: change
max(prev1, prev2 + x) to max(prev1, prev2 * x),
and initialize prev2 = prev1 = 1 (the multiplicative
identity). You've just defined a new problem: "maximum-product subset of
non-adjacent houses." Run it on [2, 3, 5, 2, 3] and
[5, 5, 5, 5, 5]. Then: under what conditions on the
input does this multiplicative version pick a different
subset of houses than the additive original? When would a robber prefer
one objective to the other?
hint
Think about which features of the input each objective rewards. Are
there inputs where the additive optimum is to spread the robs out,
but the multiplicative optimum is to concentrate them on a few big
values?
small
The problem statement says houses contain non-negative cash. What if
some entries are negative — entering the house costs you
something (alarm fee, broken window, etc.) and you'd only rob it if
it's net positive after the cost? Run the unmodified code on
[5, -10, 5]. Is the answer right? Now try
[-3, -1, -4] — every house is a loss. The code returns
0. Is that the right answer to a real-world version of the
problem, where robbing nothing might not be an option?
hint
The code has an implicit "rob nothing, score 0" option always
available. Find where in the code that option lives. What would you
change if that option were forbidden?
small
Soften the constraint instead of removing it. Suppose you can
rob two adjacent houses, but doing so costs a fixed penalty
P (the alarm triggers and you pay a fine). At
P = 0 the constraint vanishes; at P = ∞ you
get the original problem back. Replace the rolling-pair version with a
version that tracks two states per index — "robbed house i"
and "didn't rob house i" — and apply the penalty only on
the rob-then-rob transition. Sweep P from 0 to infinity on
[2, 7, 9, 3, 1] and plot the answer. Where does the
optimum's structure change, not just its value?
hint
The state per index needs to record whether the previous house was
robbed — the penalty triggers only on a rob-then-rob transition, so
the recurrence can't be summarized by "best loot up to here" alone.
Once you have that, the answer sweeps continuously in P
except at discrete thresholds where the optimum jumps to a different
subset.
medium
Tighten the constraint instead. What if up to two consecutive
houses can be robbed, but never three in a row? Modify the
rolling-pair version. The key question first: how much state do you
need now? You'll discover the original "prev1, prev2" pair isn't
enough — and figuring out the right state is the whole point of the
mod. Test on [10, 10, 10, 10, 10]: the original returns
30 (houses 0, 2, 4); your new version should return 40 (houses 0, 1, 3, 4).
hint
Two state values per index aren't enough. What does the algorithm
need to know about the recent rob history to decide whether the next
rob is allowed? Once you find the right state, the rest of the
recurrence falls out the same way the original one did.
medium
Generalize the adjacency rule completely. Instead of "you can't rob
two adjacent houses" (i.e., a one-house gap is required), require
k houses between any two robs. The original problem is
k = 1. k = 0 is "rob everything."
k = ∞ is "rob at most one." Write a parametrized
rob_k(nums, k) that works for any non-negative
k. What's the recurrence? Can you still get O(1) space, or
does k show up in the space bound?
hint
At k = 1 the recurrence reaches back 2 steps. At
k = 5, how far back does it need to reach? What state
does the algorithm need to keep around to support arbitrary
k? The space bound and the answer go together.
Variations worth knowing
House Robber II (circular street): first and
last houses are adjacent. Run the linear version twice —
excluding the first house, then excluding the last — and take
the max.
House Robber III (binary tree): houses arranged
in a tree; the constraint is "no parent-child both robbed".
Tree DP: each subtree returns a pair (rob, not_rob).
Delete and Earn: rephrase the bucketised sums of
each value as houses in a row; same recurrence.
Maximum independent set on a general graph:
NP-hard. The path/tree special cases above are the rare
polynomial-time DPs.
Climbing stairs / Fibonacci: same shape of
recurrence, different combine rule. The "rolling pair" pattern is
the same.