Pattern Recognition Drill
Medium Dynamic Programming
The Problem
Max amount you can rob without robbing two adjacent houses.
What approach would you use?
Think about it before scrolling down.
dp[i] = max(dp[i-1], dp[i-2] + val[i]). Include or exclude each house. O(n) time, O(1) space.
Common Trap
Greedy (always rob the largest) fails — adjacent constraint makes local greedy suboptimal.