Learning Outcome
After this lesson, you should be able to model adjacent restrictions with a pick-or-skip recurrence.
Problem Statement
Given money in a row of houses, return the maximum amount you can rob without robbing adjacent houses.
| Input | Output | Why |
|---|---|---|
nums = [2,7,9,3,1] | 12 | Rob houses with values 2, 9, and 1 for total 12. |
Brute Force Approach
Try every subset and reject subsets with adjacent houses. This grows exponentially.
Optimized Approach
For each house, choose max(skip current, rob current plus best before previous). Keep two rolling best values.
Exact Pseudocode
prev2 = 0
prev1 = 0
for money in nums:
current = max(prev1, prev2 + money)
prev2 = prev1
prev1 = current
return prev1Reference Code
class Solution:
def rob(self, nums):
prev2 = 0
prev1 = 0
for money in nums:
current = max(prev1, prev2 + money)
prev2 = prev1
prev1 = current
return prev1Sample Dry Run
| Step | State | Result |
|---|---|---|
| Money 2 | max(0, 0+2) | best = 2 |
| Money 7 | max(2, 0+7) | best = 7 |
| Money 9 | max(7, 2+9) | best = 11 |
| Money 1 | max(11, 11+1) | best = 12 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | Each house is processed once. |
| Space | O(1) | Only two previous best values are stored. |
Edge Cases
- Empty input should return 0.
- Single house returns that house value.
- Do not rob adjacent houses even if both are large.
Interview Checklist
- Separate skip-current and take-current choices.
- Use the old prev1 before overwriting prev2.
- Return the best up to the last house.
FAQs
What does prev1 mean?
It is the best value up to the previous house.
What does prev2 mean?
It is the best value up to the house before the previous one.
What is the core pattern?
Pick-or-skip DP.