LeetCode 198 ·
Medium
House Robber
Maximise the loot without robbing two adjacent houses.
Try it
Step through the core mechanic. The simulator below runs the dynamic programming shape this problem is built on.
Interactive · House Robber — best(i) best(i) = max(best(i−1), best(i−2) + nums[i])
| 2 | 7 | · | · | · | · |
279318
base cases seeded
The approach
best(i) = max(best(i−1), best(i−2) + nums[i]): skip house i, or rob it and add the best up to i−2. Two rolling variables suffice.
| Aspect | Value |
|---|---|
| Pattern | Dynamic programming |
| Recognise it by | Max sum with no two adjacent picks. |
| Time complexity | O(n) |
| Space complexity | O(1) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.