DPDynamic Programming
House Robber
Maximize the sum of chosen array elements with no two adjacent — a take-or-skip 1D DP with two rolling variables.
2
0
7
1
9
2
3
3
1
4
8
5
4
6
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 2 | 7 | · | · | · | · | · |
1/12Base cases: with one house rob it (2); with two houses rob the richer one (7) because adjacent houses cannot both be robbed.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn House Robber →
1dp[0] = v[0]; dp[1] = max(v[0], v[1])2for i in 2 .. n-1:3 take = dp[i-2] + v[i]4 skip = dp[i-1]5 dp[i] = max(take, skip)6return dp[n-1]Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed