DPAlgorithmaka maximum sum of non-adjacent elements, no two adjacent

House Robber

Maximize the sum of chosen array elements with no two adjacent — a take-or-skip 1D DP with two rolling variables.

▶ VisualizePattern: Dynamic ProgrammingPractice (2)
Progress

Overview

Houses along a street hold nums[i] money; robbing two adjacent houses triggers an alarm. Maximize the loot. For [2, 7, 9, 3, 1] the answer is 12 (2 + 9 + 1). The problem is the simplest "take or skip with a constraint" DP and the template for a large family: circular streets (House Robber II), trees (House Robber III, see Tree DP), and "delete and earn".

Its state and iteration are identical to Climbing Stairs, but the combination rule is max over two choices instead of a sum — a good illustration that DP problems differ mainly in the transition, not the skeleton.

1D DPtake or skipnon-adjacentO(n)O(1) spacestate machine

Intuition

A mental model before the formal terms.

Stand at the last house. Either you rob it — then the previous house is off-limits and you get nums[i] + (best loot from houses 0..i-2) — or you skip it and keep (best loot from houses 0..i-1). Whichever is bigger is the best loot from houses 0..i.

For [2, 7, 9, 3, 1]: best up to house 0 is 2; up to house 1 is max(2, 7) = 7; up to house 2 is max(7, 9 + 2) = 11; up to house 3 is max(11, 3 + 7) = 11; up to house 4 is max(11, 1 + 11) = 12. Note that greedy "take the biggest, skip its neighbors" also gives 12 here but fails on [2, 1, 1, 2] (greedy: 2 + 1 = 3, optimal 4).

How it works

  1. State: dp[i] = maximum money obtainable from houses 0..i (inclusive), whether or not house i is robbed.
  2. Transition: dp[i] = max(dp[i-1], nums[i] + dp[i-2]) — skip house i, or rob it and add the best from two houses back.
  3. Base case: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]). With a sentinel dp[-1] = 0 the loop can start at i = 0.
  4. Iteration order: i from left to right.
  5. Answer location: dp[n-1].
  6. Space optimization: two rolling variables prev2 = dp[i-2], prev1 = dp[i-1]. An equivalent two-state formulation keeps robbed (best ending with house i robbed) and skipped (best with house i not robbed): robbed' = skipped + nums[i], skipped' = max(robbed, skipped) — this is the State Machine DP view.

Why it works

Optimal substructure: any valid selection over houses 0..i either includes house i or not. If it does, it cannot include i-1, so the rest is a valid selection over 0..i-2 — and it must be the optimal one, or we could swap in a better one. If it does not include i, it is a valid selection over 0..i-1, again necessarily optimal. So the max of the two cases is exact.

The dp[i] definition deliberately means "best over the prefix" rather than "best ending at i"; that is what lets the skip branch be a plain dp[i-1] without further casework.

Only n states with O(1) work each, versus 2^n subsets in brute force.

Recognition

How to tell a problem wants this.

  • "Cannot pick two adjacent / consecutive elements", "choose elements with a gap of at least one".
  • Maximize a sum under a local exclusion constraint on a line.
  • Circular versions: solve twice on nums[0..n-2] and nums[1..n-1].
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

2
0
7
1
9
2
3
3
1
4
8
5
4
6
0123456
27·····
1/12Base cases: with one house rob it (2); with two houses rob the richer one (7) because adjacent houses cannot both be robbed.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn House Robber →
1dp[0] = v[0]; dp[1] = max(v[0], v[1])
2for i in 2 .. n-1:
3  take = dp[i-2] + v[i]
4  skip = dp[i-1]
5  dp[i] = max(take, skip)
6return dp[n-1]
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1prev2 = 0, prev1 = 0
2for x in nums:
3  cur = max(prev1, prev2 + x)
4  prev2 = prev1
5  prev1 = cur
6return prev1

Implementations

1# House robber: maximise the sum of a subset with no two adjacent elements.
2# dp[i] = max(dp[i-1], dp[i-2] + a[i]) — skip this house, or take it and
3# inherit from two back. Only two previous values matter, so O(1) space.
4 
5 
61 · Rolling two-variable form: prev2 = dp[i-2], prev1 = dp[i-1]
7def rob(a: list[int]) -> int:
8    prev2 = prev1 = 0
9    for x in a:
102 · Take x (adding dp[i-2]) or skip it (keeping dp[i-1])
11        prev2, prev1 = prev1, max(prev2 + x, prev1)
12    return prev1
13 
14 
153 · Circular street: house 0 and house n-1 are now adjacent
16def rob_circular(a: list[int]) -> int:
17    n = len(a)
18    if n == 0:
19        return 0
20    if n == 1:
21        return a[0]
22    # Either skip the last house, or skip the first — never both ends together
23    return max(rob(a[:-1]), rob(a[1:]))
24 
25 
264 · Recovering which houses were robbed needs the full dp array
27def rob_which(a: list[int]) -> list[int]:
28    n = len(a)
29    if n == 0:
30        return []
31    dp = [0] * (n + 1)
32    dp[1] = a[0]
33    for i in range(2, n + 1):
34        dp[i] = max(dp[i - 1], dp[i - 2] + a[i - 1])
35 
365 · Walk back: a house was taken iff dp[i] came from dp[i-2] + a[i-1]
37    chosen: list[int] = []
38    i = n
39    while i > 0:
40        if i >= 2 and dp[i] == dp[i - 1]:
41            i -= 1  # this house was skipped
42        else:
43            chosen.append(i - 1)
44            i -= 2  # this house was taken, so skip its neighbour
45    return chosen[::-1]
Walkthrough
  1. prev2, prev1 = prev1, max(prev2 + x, prev1) is the simultaneous update in one statement — the right-hand side is fully evaluated before either name is rebound, so no temporaries are needed.
  2. That single line is the clearest expression of the rolling recurrence in any of the four languages, and it removes the ordering bug the other three can make.
  3. a[:-1] and a[1:] build the circular sub-problems; both copy, which is the same cost as the other languages.
  4. chosen[::-1] reverses into a new list, matching the list[int] return type — chosen.reverse() would return None.
  5. The reconstruction uses an explicit while because the step depends on the branch, which a for over a range cannot express.
Complexity (this implementation)
time O(n) for all three · space O(1) for rob, O(n) for rob_which and the circular slices
Language notes
  • Tuple assignment evaluates the whole right-hand side first, which is exactly what a simultaneous DP update needs and what the other three languages must arrange manually.
  • a[:-1] is the idiomatic "all but the last"; negative slice bounds are a Python (and JS) convenience C++ lacks.
  • chosen[::-1] returns a new list while list.reverse() returns None — a recurring source of accidental None returns.
  • functools.lru_cache on a recursive formulation is the memoised alternative, but it uses O(n) stack and hits the recursion limit around n = 1000.
Common mistakes in this language
  • Writing return chosen.reverse(), which returns None.
  • Using the recursive memoised form on a large input and hitting RecursionError.
  • Initialising prev1 = a[0] instead of 0, which breaks the empty-list case.
Language differences that matter here
  • Simultaneous update: Python tuple assignment expresses prev2, prev1 = prev1, max(...) directly, while C++ and JS/TS must compute into temporaries first or get the ordering wrong — a real bug the Python form cannot make.
  • Negative slice indices (a[:-1], a.slice(0, -1)) exist in Python and JS/TS; C++ needs explicit iterator arithmetic.
  • Reversal: C++ std::reverse and JS/TS Array.prototype.reverse mutate and are chainable; Python list.reverse() returns None, so the slice form is the expression.
  • Recursion is a viable alternative only in C++ and JS/TS at this scale — CPython would hit RecursionError on a list of a few thousand houses.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Tabulated array version uses O(n) space; the tree variant is O(n) over the tree with two values per node.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Maximize a sum with a "no two adjacent" (or "gap ≥ k", with a window of k rolling values) constraint.
  • Delete and Earn: bucket values by number, then House Robber over the value axis.
  • Circular arrays via two linear runs; trees via post-order with (rob, skip) pairs.
Avoid it when
  • The constraint is a global count ("pick exactly k") rather than adjacency — that needs a second DP dimension.
  • Elements must be contiguous — that is Kadane's Algorithm.
  • Adjacency is defined by an arbitrary graph — maximum weight independent set is NP-hard in general.

Alternatives

Kadane's AlgorithmClimbing StairsState Machine DPTree DP

Common mistakes

  • Greedy "take every other house" or "take the largest and skip neighbors" — fails on [2, 1, 1, 2].
  • Defining dp[i] as "best ending at i" and then forgetting that the answer is max(dp) rather than dp[n-1].
  • House Robber II: forgetting the n == 1 case, where both slices are empty.
  • Mis-ordering the rolling update so prev1 is overwritten before prev2 reads it.

Interview patterns

  • House Robber I, II (circular), III (binary tree).
  • Delete and Earn: transform to House Robber over value counts.
  • Maximum sum with no two adjacent in a 2D grid (row-wise then column-wise) — Pizza With 3n Slices style extensions.
  • Stock problems with cooldown — same two-state machine with an extra state.
Interview questions on this
Mock interviews

Example problems

Climbing StairseasyHouse Robbermedium