1-D Linear DP: House Robber Family

In linear DP the answer at position i depends on a few positions right before it. House Robber is the reference problem: take house i and skip i-1, or skip i and keep the best so far. Learn it well, because many problems turn out to be House Robber once you look at them from a slightly different angle.

The idea#

Let best(i) be the most you can collect from the first i items. At item i you have two choices:

Skip it: best(i-1).
Take it: value[i] + best(i-2), because taking i rules out i-1.

best(i) = max(best(i-1), value[i] + best(i-2)).

Why does this work? The future only needs to know the best total up to each of the last two positions. Those are the only two numbers you keep, so the table shrinks to two variables.

How to spot it#

Since so many problems reduce to House Robber, the skill is spotting the shape behind a new story. Look for these signals in the question.

A line of items (houses, days, digits) and a rule about neighbors: "can't take adjacent", "one or two steps", "one or two digits".
The answer at i only looks back a fixed distance (1, 2, or a jump to "the next free index").
Taking a value blocks its neighboring values. Index by value and the values become a line.
Constraints around $10^4$ to $10^5$ , which rule out anything worse than $O(n)$ or $O(n \log n)$ .

Template#

Here is the recurrence from above written with two rolling variables instead of a table. It runs in $O(n)$ time and $O(1)$ space.

prev2 = 0                         # best up to i-2
prev1 = 0                         # best up to i-1
for each value v in the line:
    current = max(prev1,          # skip this item
                  v + prev2)      # take it, so skip the neighbor
    prev2 = prev1
    prev1 = current
return prev1

Other members of the family change what you look back at: the last three answers, a branch on one or two digits, or a jump to the next free index. The rolling idea stays the same.

Pitfalls#

These mistakes cause the most wrong answers.

Carrying a "blocked" set into each recursive call, which is a common first try when taking one item rules out others. That set can't be used as a cache key, so the search stays exponential. Reframe the problem so the set is not needed.
Forgetting tiny inputs. When you split a problem into runs on slices, a slice can be empty.
Accepting codes with a leading zero when you parse digits. Check the exact valid range.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with House Robber.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: House Robber

This is the template as written: skip the house, or take it and add the best from two houses back.

Hint: House Robber II

The first and last houses are now neighbors, so they can't both be taken. Run the line version twice, once without the first house and once without the last, and take the max. Handle a single house separately: both slices are empty and the answer is that house.

Hint: Delete and Earn

Taking value x means you can't take x-1 or x+1. Bucket the points by value (points[x] += x for every copy), then run House Robber over the values 0..max(nums). A missing value has 0 points. Check: [2, 2, 3, 3, 3, 4] gives buckets [0, 0, 4, 9, 4] and answer 9.

Hint: Climbing Stairs

The ways to reach step i are the ways to reach i-1 plus the ways to reach i-2. Steps 0 and 1 have one way each.

Hint: Min Cost Climbing Stairs

Combine the last two answers again, but take the min and add the step's cost.

Hint: N-th Tribonacci Number

Same rolling idea with three variables instead of two.

Hint: Decode Ways

Branch on a 1-digit or 2-digit code. Add ways(i-1) if s[i-1] is '1'..'9', and ways(i-2) if s[i-2:i] is "10".."26". A '0' can only be part of 10 or 20, and "06" is not a valid code.

Hint: Minimum Cost For Tickets

At each travel day, try a 1-day, 7-day or 30-day pass. A pass covers every travel day before day + duration, so the next state is the first uncovered day, not i + 1. Find that index with a short scan or bisect to stay linear or $O(n \log n)$ .

Key takeaways#

best(i) = max(best(i-1), value[i] + best(i-2)) is the core recurrence.
Two rolling variables replace the whole table.
A circular line is two linear runs with one end removed each time.
When taking x blocks x-1, index by value and the problem becomes House Robber.
The "previous" state can be a jump (next uncovered day), not only i-1.

Core idea#

The answer at position i depends on a few positions right before it. House Robber is the reference: best(i) = max(best(i-1), value[i] + best(i-2)).

Key points#

Skip item i and keep best(i-1), or take it and add best(i-2).
The future needs only the best totals at the last two positions. Two rolling variables replace the table.
Spot it: a line of items and a rule about neighbors ("can't take adjacent", "one or two steps").
Constraints near $10^4$ to $10^5$ point to $O(n)$ or $O(n \log n)$ .
When taking x blocks x-1, index by value. Delete and Earn becomes House Robber.
The "previous" state can be a jump, not only i-1.

Variations#

Problem	Change
House Robber II (circular)	Max of two runs: without the first, without the last
Climbing Stairs, Tribonacci	Sum the last two or three answers
Decode Ways	Add `ways(i-1)` for `'1'..'9'`, `ways(i-2)` for `"10".."26"`
Min Cost for Tickets	Next state is the first uncovered day

Template#

prev2 = prev1 = 0                 # best up to i-2, best up to i-1
for each value v in the line:
    current = max(prev1, v + prev2)   # skip, or take and skip neighbor
    prev2, prev1 = prev1, current
return prev1
Delete and Earn: points[x] += x, then run this over values 0..max

Pitfalls#

Passing a "blocked" set of taken items into each call. The set cannot be a cache key, so the search stays exponential.
Forgetting the single-house case in the circular version.
Treating "06" as a valid two-digit code in Decode Ways.

Say it in an interview#

"Take this house and skip the neighbor, or skip this house. Two variables are enough."
"Taking x blocks x-1, so bucket by value and run House Robber."