At every house i you face a binary choice: rob it (and add its money to whatever the best haul was up through house i-2, since i-1 is now off-limits) or skip it (and keep whatever the best haul was through i-1). Taking the better of those two options at each step is the entire algorithm.
Brute Force Recursion
Time O(2ⁿ)Space O(n)Define helper(i) as the max money obtainable using only houses 0..i. At house i, either skip it (helper(i-1)) or rob it and add to the best from two houses back (helper(i-2) + nums[i]).
class Solution: def rob(self, nums: list[int]) -> int: def helper(i: int) -> int: if i < 0: return 0 return max(helper(i - 1), helper(i - 2) + nums[i]) return helper(len(nums) - 1)Each call spawns two more, so the call tree doubles with depth → O(2ⁿ) time, even though only n distinct values of i ever occur (huge redundant recomputation).
Top-Down Memoization
Time O(n)Space O(n)Cache helper(i) so each of the n distinct subproblems is solved exactly once.
class Solution: def rob(self, nums: list[int]) -> int: memo = {} def helper(i: int) -> int: if i < 0: return 0 if i in memo: return memo[i] memo[i] = max(helper(i - 1), helper(i - 2) + nums[i]) return memo[i] return helper(len(nums) - 1)n subproblems, O(1) work each beyond memoized recursive calls → O(n) time, O(n) space for the memo and call stack.
Bottom-Up DP
OptimalTime O(n)Space O(n)Build dp[i] = max money robbable from houses 0..i, filled left to right: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
class Solution: def rob(self, nums: list[int]) -> int: n = len(nums) if n == 1: return nums[0] dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) return dp[-1]Trace for nums = [2, 7, 9, 3, 1]:
dp[0] = nums[0] = 2. Only one house, so rob it.
One pass, constant work per house → O(n) time. Since dp[i] only ever needs the previous two entries, the array can be collapsed to two rolling variables for O(1) space, but the full array is shown here for clarity.