#198
House Robber
Medium 1D DP (take / skip)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Houses in a row hold money. You can't rob two adjacent houses. Return the most money you can rob.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: rob houses without robbing two neighbours.
Why this works: at each house, either rob it (plus the best two houses back) or skip it (the best one house back).
Example: [2, 7, 9, 3, 1]
best: 2, 7, 11, 11, 12 → 12 (2 + 9 + 1)✦Hints open one at a time
At house i, either rob it (plus the best up to i − 2) or skip it (best up to i − 1).
dp[i] = max(dp[i − 1], dp[i − 2] + nums[i]).
↗Approach
Keep the best totals for the previous two positions and roll them forward.
</>Solution (Java)
class Solution {
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0; // best up to i-2, i-1
for (int x : nums) {
int cur = Math.max(prev1, prev2 + x); // skip vs rob
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}!Common mistake
Robbing all even or all odd houses — the best choice can skip two in a row.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon