House Robber: Learning Dynamic Programming Through a Classic Interview Problem
3 views
"House Robber" is one of the friendliest ways interviewers introduce dynamic programming. You're given an array where nums[i] is the amount of money in house i. You can't take from two adjacent houses (the alarm system links neighbors). Return the maximum total you can take.
Example: [2, 7, 9, 3, 1] gives 12, by taking houses 0, 2 and 4 (2 + 9 + 1).
Why greedy fails
A natural first idea is to always grab the largest remaining value, or to alternate even and odd indices. Both break quickly. For [2, 1, 1, 2], the even indices give 3 and the odd ones give 3, but the best answer is 4 (first and last house). Saying this out loud shows the interviewer you checked your intuition before committing to it.
Defining the state
Let best[i] be the most money you can collect from the first i houses. For house i, you have exactly two choices:
- Skip it: the total is best[i - 1].
- Take it: you can't take house i - 1, so the total is best[i - 2] + nums[i].
So best[i] = max(best[i - 1], best[i - 2] + nums[i]). The base cases are best[0] = nums[0] and best[1] = max(nums[0], nums[1]).
Bottom-up with constant space
Each step depends only on the previous two values, so you don't need the whole table:
def rob(nums):
prev2, prev1 = 0, 0
for money in nums:
prev2, prev1 = prev1, max(prev1, prev2 + money)
return prev1
This runs in O(n) time and O(1) space. Starting both variables at 0 handles empty and single-element arrays without special cases, which is worth pointing out.
Top-down alternative
Some candidates think more naturally in recursion. A memoized version, rob(i) = max(rob(i + 1), nums[i] + rob(i + 2)), is completely acceptable. Mention that it uses O(n) stack space and could hit recursion limits for large inputs, then offer the iterative version.
Follow-up 1: houses in a circle
In "House Robber II", the first and last houses are neighbors. The trick is to run the linear solution twice: once on nums[1:] (exclude the first house) and once on nums[:-1] (exclude the last), then take the max. Handle a single house separately.
Follow-up 2: houses on a tree
In "House Robber III", the houses form a binary tree, and you can't rob a parent and child together. Do a post-order traversal that returns a pair for each node: (best if this node is robbed, best if it isn't). If robbed, the children must be skipped. If skipped, each child contributes its own max. This is a nice bridge from array DP to tree DP.
How to present it in an interview
1. Give a counterexample to greedy.
2. Define the state in one sentence.
3. Write the recurrence and base cases.
4. Code the O(1) space version.
5. Trace [2, 7, 9, 3, 1] by hand.
That flow, from the problem to the state, then the recurrence, then the optimization, works for most one-dimensional DP questions, including climbing stairs, decode ways and min cost climbing stairs.
If you tend to freeze when it's time to define the state with an interviewer watching, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews so you can keep your reasoning structured.