The instinct that sinks people on House Robber is to rob every other house. It feels safe, since you never touch two neighbors. On [5, 1, 1, 5] that hands you 6 when the answer is 10, because the two 5s sit at the ends, aren’t adjacent, and you’re free to take both. The problem (LeetCode 198) gives you a row of houses holding nums[i] dollars each, forbids robbing two adjacent houses, and asks for the largest total you can carry off. The alarm wiring between neighbors is the only constraint, and it drives everything.
The one decision, repeated down the row
Stand at house i with every earlier house already settled. You have two moves and no others. Rob it, which means house i-1 had to be skipped, so your total is nums[i] plus the best you could manage through house i-2. Or leave it, and carry forward the best total through i-1. The maximum through house i is whichever is larger:
best(i) = max(best(i-1), nums[i] + best(i-2))That recurrence is the whole problem. Everything after this is bookkeeping about computing it without repeating work you’ve already done.
Why the naive recursion is a trap
Translate the recurrence straight into recursion and you get code that reads fine and runs like molasses:
def rob(nums):
def best(i):
if i < 0:
return 0
return max(best(i - 1), nums[i] + best(i - 2))
return best(len(nums) - 1)Correct, and O(2^n). Computing best(i) calls best(i-1) and best(i-2), then best(i-1) turns around and calls best(i-2) again, and the recomputation fans out into an exponential tree. At n = 40 you’re waiting a while. When an interviewer asks for the time complexity right here, they’re checking whether you notice the overlapping subproblems, which is the tell that dynamic programming applies at all. Same best(i-2), two different parents, one answer, computed twice.
Cache each result the first time you compute it and the tree collapses. Every repeat call becomes a lookup, which drops you to O(n) time and O(n) space for the cache and the recursion stack:
from functools import cache
def rob(nums):
@cache
def best(i):
if i < 0:
return 0
return max(best(i - 1), nums[i] + best(i - 2))
return best(len(nums) - 1)Plenty of interviewers take this and move on. Some will nudge you toward the bottom-up version, because it makes the space story cleaner and shows you understand which subproblems have to be ready before which.
Bottom-up, then down to two variables
Fill an array left to right, each cell holding the best total through that house:
def rob(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], nums[i - 1] + dp[i - 2])
return dp[n]The offset by one keeps dp[0] as the empty prefix, so you never index off the front. Now notice what dp[i] actually reads: only dp[i-1] and dp[i-2]. The rest of the array is dead weight. Hold two running numbers instead and the space falls to O(1):
def rob(nums):
rob_prev, skip_prev = 0, 0
for cash in nums:
rob_here = skip_prev + cash
skip_here = max(rob_prev, skip_prev)
rob_prev, skip_prev = rob_here, skip_here
return max(rob_prev, skip_prev)The variable names are deliberate, because this is where the pattern the problem is really teaching shows up.
The state machine hiding inside it
At every house you’re in one of two states: you just robbed this one, or you didn’t. Carry the best money reachable in each state as you walk the row. To sit in the robbed-here state you had to arrive from didn’t-rob-the-last-one and add this house’s cash. To sit in the didn’t-rob-here state you could have come from either state before it, so you take the larger. Two states, fixed transitions, one pass. That is a state machine, and the dynamic programming is nothing more than pushing the best value in each state forward one step at a time.
| State after visiting house i | What it means | Legal previous state | Best value in this state |
|---|---|---|---|
| robbed house i | you took nums[i], so house i-1 had to be left alone | skipped house i-1 | skip(i-1) + nums[i] |
| skipped house i | you left nums[i] where it was | robbed or skipped house i-1 | max(rob(i-1), skip(i-1)) |
Naming it a state machine isn’t decoration. It’s the lever that carries you through the follow-ups without inventing anything new, and it’s the thing a strong candidate says out loud to show they’ve met the shape before. Any time a problem has a small fixed set of situations you can be in and legal transitions between them, with a value to maximize, reach for this.
When they ask which houses you actually robbed
The two-variable version throws away the detail you’d need to name the houses, so when the follow-up is “which ones,” go back to the array and walk it backward. Standing at dp[i], if it equals dp[i-1] then house i-1 was skipped; otherwise it was robbed and you jump back two:
def rob_which(nums):
n = len(nums)
dp = [0] * (n + 1)
if n:
dp[1] = nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2])
robbed, i = [], n
while i > 0:
if dp[i] == dp[i - 1]:
i -= 1
else:
robbed.append(i - 1)
i -= 2
return dp[n], robbed[::-1]On [2, 7, 9, 3, 1] this returns 12 along with houses 0, 2, and 4, the plan that beats grabbing the single largest pile.
House Robber II: the row bent into a circle
LeetCode 213 joins the ends, so house 0 and house n-1 are neighbors now. The recurrence doesn’t change, but the wrap-around creates a conflict: the two ends can’t both be robbed. The clean move is to see that any valid plan leaves at least one end alone, so run the linear solver twice, once over houses 0 through n-2 and once over 1 through n-1, and keep the better result. Guard the single-house case, where both slices come out empty:
def rob(nums):
if len(nums) == 1:
return nums[0]
def rob_line(houses):
rob_prev, skip_prev = 0, 0
for cash in houses:
rob_prev, skip_prev = skip_prev + cash, max(rob_prev, skip_prev)
return max(rob_prev, skip_prev)
return max(rob_line(nums[:-1]), rob_line(nums[1:]))House Robber III: the houses form a tree
LeetCode 337 lays the houses out as a binary tree, and the rule becomes that you can’t rob a node together with its direct children. The two-states-per-house idea survives untouched; only the traversal changes. Do a post-order walk and have each node return a pair, the best total if you rob it and the best if you don’t. Robbing a node adds its value and forces both children to be skipped. Skipping it lets each child pick its own better option on its own:
def rob(root):
def visit(node):
if not node:
return (0, 0) # best if we rob this node, best if we skip it
l_rob, l_skip = visit(node.left)
r_rob, r_skip = visit(node.right)
rob_here = node.val + l_skip + r_skip
skip_here = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob_here, skip_here)
return max(visit(root))Same two states, same transitions, walked over a tree instead of a straight line. If you framed the original as a state machine, this one mostly writes itself, which is why interviewers like running the three in sequence.
Where the same machine turns up again
Tracking the best value reachable in each of a few states covers a wide swath of the DP questions that get asked, and House Robber is only the doorway in. Best Time to Buy and Sell Stock with Cooldown (LeetCode 309) runs on three states, holding, sold today, and free, with fixed moves between them, and you solve it the way you solved House Robber, one pass carrying a small set of running maxima. Delete and Earn (LeetCode 740) is House Robber in a costume: bucket the values by amount, and taking value k locks out k-1 and k+1, which is the adjacency rule wearing different clothes. Paint House, with a per-row cost for each color choice, is the same machine with three states in place of two.
If your interview stops at 198, the move before you write a line of code is to say which two numbers you plan to carry and why, then state the transition into each state. That sentence is what separates someone who memorized the O(1) trick from someone who can rebuild it under a follow-up they’ve never seen.
Drill the patterns next:
