House Robber

A row of houses each holds some amount of money. You cannot rob two adjacent houses on the same night because their security systems are linked and would trigger an alarm. Given the amounts, return the maximum total you can rob.

Example#

For nums = [2, 7, 9, 3, 1] the best plan robs houses 0, 2, and 4 for 2 + 9 + 1 = 12. For nums = [1, 2, 3, 1] the best is houses 0 and 2 for 1 + 3 = 4.

Brute force note#

Trying every valid subset of non-adjacent houses is exponential. A recursive “rob this house and skip the next, or skip this house” branching recomputes the same suffixes repeatedly.

Optimal approach#

Let best(i) be the most money robbable from the first i houses. At house i you either skip it, keeping best(i-1), or rob it, adding nums[i] to best(i-2). So best(i) = max(best(i-1), best(i-2) + nums[i]). You only need the two previous results, so track them in two rolling variables.

 1def rob(nums):
 2    prev2, prev1 = 0, 0  # best up to i-2 and i-1
 3    for money in nums:
 4        prev2, prev1 = prev1, max(prev1, prev2 + money)
 5    return prev1
 6
 7
 8print(rob([2, 7, 9, 3, 1]))  # 12
 9print(rob([1, 2, 3, 1]))     # 4
10print(rob([]))               # 0

Complexity#

Time is O(n): one pass over the houses. Space is O(1) using two rolling variables instead of an O(n) table.

This is a classic linear DP with a skip-or-take choice. Reinforce the pattern on the dynamic programming topic page, then continue through the 60-day curriculum.