15. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. Adjacent houses have security systems connected, so you cannot rob two adjacent houses on the same night.
How It Works & Algorithmic Design
Solves using Dynamic Programming Choice State:
- Choice at House $i$:
- Option 1: Rob House $i$ $\to$ gain
money[i]+ maximum money from house $i-2$ (prev2 + money[i]). - Option 2: Skip House $i$ $\to$ keep maximum money from house $i-1$ (
prev1).
- Option 1: Rob House $i$ $\to$ gain
- DP Formula:
curr = Math.max(prev1, prev2 + money[i]). - State Update: Advance
prev2 = prev1andprev1 = curr.
Why This Approach Works Best
Solves non-adjacent maximum sub-sequence sum problems in linear $O(n)$ time and constant $O(1)$ space.
Example Walkthrough
Input:
[2, 7, 9, 3, 1]Money in each house.
Optimal Path:
Rob house 1 ($2) + house 3 ($9) + house 5 ($1) = 12Non-adjacent selection.
Output:
12Maximum stolen total.
Answer: House Robber DP implementation
function rob(nums) {
let prev2 = 0, prev1 = 0;
for (const num of nums) {
const curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}💡 Decide at each house whether to rob it or skip it to optimize accumulated loot.
Key Takeaways
- At each element, choose between robbing current item or keeping previous sub-total.
- Space optimized to $O(1)$ by tracking only two previous state variables.
- Linear time complexity $O(n)$.