Dynamic Programming · LC #198
House Robber
Maximise the sum of non-adjacent elements in an array using a two-variable rolling DP. At each house, pick the better of skipping or robbing.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Rob houses in a row. You cannot rob adjacent houses. Maximise total money.
Sample I/O
Input: nums = [1,2,3,1] Output: 4 (rob house 1 and 3) Input: nums = [2,7,9,3,1] Output: 12 (rob house 1, 3, 5)
Intuition
How to Think About It
Intuition
DP works because the best loot up to house i depends only on the best loot up to i-1 (skip) and i-2 (rob i). Overlapping subproblems make memoisation / tabulation reduce exponential recursion to linear.
Core Concept
Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Rolling vars: prev1 = best ending at or before previous house; prev2 = best ending at or before two houses back.
When to use
Maximum sum / selection problems with an adjacency constraint - house robber, stock cooldown, task scheduler with gaps.
When NOT to use
When the constraint is not strictly "no two adjacent" but a more complex dependency graph - model as a general graph DP instead.
Key Insights
What to Know Cold
- Two rolling variables fully encode the DP state - no array needed.
- Initialise both to 0; the loop handles all positions including a single-element array.
- The "skip" choice (prev1) always carries forward the best seen so far, not just the previous element.
- This is the 1D knapsack where item weights are 1 and adjacency is the conflict constraint.
- House Robber II wraps this in two sub-range calls to handle the circular constraint.
1 example
Worked Examples
Rob [2,7,9,3,1]
Five houses; cannot rob adjacent. Find max loot.
Rolling DP: track best-so-far and best-excluding-last.
Output: 12
Template for all "no-adjacent-selection" DP problems; House Robber II and the circular variant build directly on this pattern.