House Robber
LeetCode 198 • Medium • Dynamic Programming
Input: nums = [2, 7, 9, 3, 1] → Output: 12
Rob max money. No two adjacent. dp[i] = max(dp[i-1], dp[i-2] + nums[i]). O(1) space with prev, curr.
TimeO(n)single pass
SpaceO(1)prev, curr
prev: —
curr: —
Ready
Press Play. For each house: curr = max(prev + nums[i], curr); prev = old curr.
TimeO(n)memoized
SpaceO(n)memo + call stack
3
Practice until you don't need to look. The green highlights are the nuances to burn into memory.
PATTERN ▸ dp[i] = max(dp[i-1], dp[i-2]+nums[i]) O(n) · O(1)
① INIT
prev, curr = 0, 0
② LOOP
for num in nums:
prev, curr = curr, max(curr, prev + num)
③ RETURN
return curr
▼ your implementation ▼
Verify your solution:
Practice until you don't need to look. Memoized recursion: rob(i) = max(rob(i-1), rob(i-2)+nums[i]).
PATTERN ▸ Memoized recursion O(n) · O(n)
① BASE CASE
if i < 0: return 0
② MEMO CHECK
if i in memo: return memo[i]
③ RECURSE & STORE
memo[i] = max(rob(i-1), rob(i-2)+nums[i])
return memo[i]
▼ your implementation ▼
Verify your solution: