All Problems
Easy Problemsoptimizationlinear

House Robber

Given a row of n houses, each holding some amount of money, choose a subset of houses to rob so that no two chosen houses are next to each other. Maximize the total amount collected.

Do this lesson first: house robber

Example input

nums = [2, 7, 9, 3, 1, 8, 10, 4, 6, 5]

Expected output

28

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]) are given; see the flagship lesson for why a single house is always taken and two adjacent houses reduce to picking the richer one. Every other cell depends only on smaller indices, so filling left to right guarantees both predecessors already hold a real value before they are read.

i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8
i=9
2
7
11
11
12
19
22
23
28
28
house-robber.ts
  1. 1function rob(nums) {
  2. 2 const dp = [nums[0], Math.max(nums[0], nums[1])];
  3. 3 for (let i = 2; i < nums.length; i++) {
  4. 4 dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
  5. 5 }
  6. 6 return dp[nums.length - 1];
  7. 7}
Base caseComputedBeing readAnswer

The code, the trap, the variations

house-robber.ts
  1. 1function rob(nums) {
  2. 2 const dp = [nums[0], Math.max(nums[0], nums[1])];
  3. 3 for (let i = 2; i < nums.length; i++) {
  4. 4 dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
  5. 5 }
  6. 6 return dp[nums.length - 1];
  7. 7}

Where people go wrong

Assuming a fixed alternate-houses pattern, rob every other house starting from house 0 or house 1, always wins. It does not: among the first six houses of this street (2, 7, 9, 3, 1, 8), robbing every even house gives 2 + 9 + 1 = 12 and robbing every odd house gives 7 + 3 + 8 = 18, but the true optimum is 19, robbing houses 0, 2, and 5 for 2 + 9 + 8, a gap pattern no fixed parity would ever try.

  • Arrange the houses in a circle, so house 0 and house n - 1 are adjacent too.

    The recurrence itself is unchanged; solve this same table twice, once excluding house 0 and once excluding house n - 1, and take the better of the two totals, since the only new conflict the circle adds is between those two ends.

  • Allow skipping at most two houses in a row, instead of only ever avoiding adjacent robberies.

    dp[i] needs three predecessors instead of two, dp[i - 1], dp[i - 2], and dp[i - 3], one bucket per how many houses back the previous robbery could have been, and the combine step still takes a max over all of them.

Min Cost Path