House Robber
Understand the problem
A robber goes down a row of houses, each holding nums[i] in cash. He can't rob 2 adjacent houses (the alarm system would trigger). Find the maximum amount he can take.
Example:
ts
nums = [1, 2, 3, 1]
output = 4 // rob house 0 (1) + house 2 (3)
nums = [2, 7, 9, 3, 1]
output = 12 // rob house 0 (2) + house 2 (9) + house 4 (1)The decision at each house: rob it (take nums[i] + profit[i-2]) or skip it (keep profit[i-1]).
Pick the larger.
Basic approach
O(2ⁿ) time, O(n) space (call stack) — each house has 2 choices, 2ⁿ recursive branches in totalts
// Top-down recursion without memoization
function robNaive(nums: number[]): number {
function dfs(i: number): number {
if (i >= nums.length) return 0
// at house i: rob it or skip it
return Math.max(
nums[i] + dfs(i + 2), // rob house i, jump to i+2
dfs(i + 1) // skip house i, move to i+1
)
}
return dfs(0)
}Why this approach is slow:
Subproblems get recomputed many times (e.g. dfs
- is called from both dfs
- and dfs(2))
Memoization or bottom-up DP eliminates this duplication.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.