House robber
Why it exists
Problem: You need to find a subsequence with maximum sum such that no two elements are adjacent. Greedily picking the largest values or every-other house fails on cases like `[2, 1, 1, 2]`.
Better idea: Make a choice at each house: rob it (and take the max money from 2 houses ago) OR skip it (and keep the max money from the previous house). Compare these two entire strategies dynamically.
Mental model
At every house, compare the best outcome of 'robbing here' versus 'skipping here'.
Let `dp[i]` represent the maximum money you can rob from the first `i` houses. The base cases are `dp[0] = nums[0]` (only one house) and `dp[1] = max(nums[0], nums[1])` (rob the better of the first two). The transition is `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`. You are not deciding if a house is 'good' in isolation; you are comparing the strategy of including it versus skipping it.
Repeated decision: Do I rob this house (skip the previous one, take its money plus what I had 2 houses ago) or skip it (keep whatever I had at the previous house)?
Explanation
This problem introduces the classic 'include or exclude' 1D choice in Dynamic Programming.
If we hand-trace the array `[2, 7, 9, 3, 1]`:
- `dp[0] = 2`
- `dp[1] = max(2, 7) = 7`
- `dp[2] = max(dp[1], dp[0] + 9) = max(7, 2 + 9) = 11`
- `dp[3] = max(dp[2], dp[1] + 3) = max(11, 7 + 3) = 11`
- `dp[4] = max(dp[3], dp[2] + 1) = max(11, 11 + 1) = 12`
Notice that the recurrence `dp[i] = max(dp[i-1], dp[i-2] + nums[i])` only looks at the previous two states. Just like Climbing Stairs, we can space-optimize this to O(1) space by keeping two rolling variables instead of the entire `dp` array.
Key points
- Complexity: O(n) time, O(1) space (with rolling variables). O(n) space if storing the full table.
Common mistakes
- Using a greedy approach: Greedily picking the largest available elements or summing all even/odd indices fails. For example, in `[2, 1, 1, 2]`, evens give 2+1=3, odds give 1+2=3, but the optimal is 2+2=4.
- Off-by-one on the adjacency check: Ensure that `dp[i-2] + nums[i]` doesn't accidentally read out of bounds when `i < 2`. Properly initialize `dp[0]` and `dp[1]` before running the loop from `i=2`.
Recall questions
- What does `dp[i]` represent in the House Robber problem?
- What is the recurrence relation for House Robber?
- Why does a greedy approach (e.g. comparing the sum of even indices to odd indices) fail for House Robber?
Questions & answers
What if the houses are arranged in a circle, so the first and last houses are adjacent?
Run the standard House Robber algorithm twice: once from house 0 to n-2, and once from house 1 to n-1. Take the maximum of the two results.
Approach: Break the circular dependency by isolating the two mutually exclusive scenarios.
How would you modify the algorithm to return the *indices* of the houses robbed?
You can no longer use O(1) space. Maintain the full `dp` array and backtrack from `dp[n-1]`: if `dp[i] == dp[i-1]`, you skipped house `i`; if `dp[i] == dp[i-2] + nums[i]`, you robbed it.
Approach: Reconstruct the path using the final DP table by reversing the `max()` decision at each step.
Continue learning
Previous: Climbing stairs / Fibonacci
Next: Coin change