House Robber

Bottom-up DP over adjacent-house choices

time O(n)space O(n)

Because you can never rob two adjacent houses, the best score at house i can only be built from a house two or more steps back — so every house's best answer is computed once and then reused, never redone. Every house poses the same binary choice: SKIP it and keep rob[i-1], or TAKE its cash plus the best from two houses back, rob[i-2] + nums[i]. Fill rob[] left to right and each entry becomes a solved subproblem the next house reuses — that reuse is the whole trick of DP.

Details

Animated on: Rob houses with values [2, 7, 9, 3, 1] without robbing two adjacent houses — maximize the loot.

Problem:House RobberMedium

Pattern:1D Dynamic Programming

Bottom-up DP over adjacent-house choices

step 1 / 9

[0]

[1]

[2]

[3]

[4]

Houses [2, 7, 9, 3, 1], and rob[i] will mean 'the most loot possible from the first i+1 houses'. Base case: with only house 0 in play, rob[0] = 2.

i=0· arr[0] = 2

Pseudocode

1FUNCTION rob(nums):
2  rob[0] = nums[0]
3  rob[1] = the larger of nums[0] and nums[1]
4  FOR i from 2 to n-1:
5    take = rob[i-2] + nums[i]
6    skip = rob[i-1]
7    rob[i] = the larger of skip and take
8  RETURN rob[n-1]

← / → step · space play · Home restart

Every step in words

Show all 9 steps

Houses [2, 7, 9, 3, 1], and rob[i] will mean 'the most loot possible from the first i+1 houses'. Base case: with only house 0 in play, rob[0] = 2.
Houses 0 and 1 are adjacent, so we can keep only one: rob[1] = max(2, 7) = 7. House 1's 7 beats house 0's 2, so the best plan so far robs house 1 alone.
House 2 (value 9). TAKE it and we must jump over house 1, adding to rob[0]: take = 2 + 9 = 11. SKIP it and we keep rob[1] = 7.
take = 11 beats skip = 7, so rob[2] = 11. The best plan flips: rob houses 0 and 2 (2 + 9 = 11) and abandon house 1 — DP happily reverses earlier choices.
House 3 (value 3). TAKE forces us back to rob[1]: take = 7 + 3 = 10. SKIP keeps rob[2] = 11. Taking a small house can cost us a big neighbor.
skip = 11 beats take = 10, so rob[3] = 11. House 3 isn't worth losing house 2's 9 over — the plan stays {house 0, house 2}.
House 4 (value 1). TAKE pairs it with rob[2]: take = 11 + 1 = 12. SKIP keeps rob[3] = 11. House 3 was skipped, so house 4 sits safely non-adjacent to house 2.
take = 12 beats skip = 11, so rob[4] = 12. Even a house worth 1 helps when it stacks on top of an already-optimal subproblem.
Done: rob[] filled as [2, 7, 11, 11, 12]. Answer = rob[4] = 12, robbing houses 0, 2, 4 (2 + 9 + 1) — no two adjacent, and every entry was computed once from two earlier entries.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve House Robber in the editor All Dynamic Programming problems Back to roadmap