House Robber
Mediumdp[i] = max(dp[i−1], dp[i−2] + nums[i])
At each house pick the better of: skip it, or rob it plus the best from two houses back.
The idea
At each house you either skip it (keep the best up to the previous house) or rob it (add its money to the best from two houses back, since adjacent houses are off-limits).
calls1
Step 1 of 7. Brute force: rob(5) calls rob(4) and rob(3) — and each of those splits again. calls 1.
1/7
Brute force
timeO(2ⁿ)spaceO(n)
Exponential tree.
1function rob(i) {2 if (i < 0) return 0;3 return Math.max(rob(i - 1), rob(i - 2) + nums[i]);4}Input
- nodes
- 1, 0 edges
Memory
- calls
- 1
- rob(1) redone
- —
- brute calls
- —
Call stack
- 0visit(rob(5))
Output
- with memo
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3, 1]
- Output:
- 4
- Explanation:
- Rob houses 1 and 3 → 1 + 3 = 4.
Example 2
- Input:
- nums = [2, 7, 9, 3, 1]
- Output:
- 12
- Explanation:
- Rob 2 + 9 + 1 = 12.
Example 3
- Input:
- nums = [5]
- Output:
- 5
- Explanation:
- One house → just take it.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.