DP II — 1D Linear

Review boundary and corrected contracts

House values are nonnegative; Delete and Earn uses positive integers. Empty lists return 0 as a local extension. The linear recurrence has constant work per state under unit-cost arithmetic. The circular reduction copies two slices as written, so its auxiliary storage is O(n), not O(1). Delete-and-Earn sorts distinct values, adding O(m log m) work.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Write the state definition as an English sentence before any code, derive the transition from that sentence, and handle the circular and value-collapsed variants of House Robber.

Series: LeetCode — From Basics to Production-Ready · Session 34 / 65 · Phase 2 · Dynamic programming

Why this session exists

Almost every DP bug I have watched someone produce traces back to the same root cause: they never said, in words, what dp[i] means. They wrote an array, wrote a plausible-looking transition, got a wrong answer, and then debugged the transition — which was never the problem.

So this session enforces one discipline. Before any code, write the sentence. Not "dp is the answer at i" — that is not a sentence, that is a shrug. The sentence has to be precise enough that someone else could verify your transition against it without seeing the problem:

dp[i] = the maximum amount robbable considering only houses 0 through i, where house i may or may not be robbed.

That "may or may not" is doing real work. The alternative definition — "the max assuming house i is robbed" — is also valid and leads to a different, equally correct transition. What is fatal is not knowing which one you chose.

The second thing this session teaches is a transformation habit. House Robber II (circular) and Delete and Earn both reduce to plain House Robber by changing the input, not by inventing a new recurrence. Reduction is a real skill and this is the cleanest place to practise it.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

dp = [0] * (n + 1)
dp[i] = f(dp[i-1], dp[i-2])

Concretely: write House Robber as a full array, then collapse it to two variables. Then, without looking, write the state definition sentence in a comment above it.

What wobbles: the two-variable collapse. Getting prev1 and prev2 assigned in the wrong order overwrites the value you still need. Write the simultaneous-assignment form and know why it works.

Pattern anatomy

The shape of problem that summons 1D linear DP: a sequence of items processed left to right, where the answer at each position depends on a bounded window of earlier positions. Bounded is the operative word. If dp[i] needs dp[j] for all j < i, that is a different family — that is session 36, and it costs O(n²).

The invariant: when the loop reaches index i, every dp[j] for j < i is final and correct under the state definition. This is why fill order matters and why you can never read forward.

The template:

def linear_dp(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [0] * n
    dp[0] = base_case_0(nums)
    if n > 1:
        dp[1] = base_case_1(nums)
    for i in range(2, n):
        dp[i] = combine(dp[i - 1], dp[i - 2], nums[i])
    return dp[n - 1]

House Robber. The state sentence: dp[i] = maximum robbable from houses 0..i inclusive, with no constraint on whether house i itself was robbed.

The transition follows from that sentence by case analysis on house i. Either you rob it — in which case you cannot have robbed i−1, so you add nums[i] to dp[i−2] — or you skip it, in which case the answer is whatever it was at i−1.

def rob(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])       # NOT nums[1]: you may prefer house 0
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[n - 1]

dp[1] = max(nums[0], nums[1]) is the base case people get wrong. Under the stated definition, dp[1] is the best over houses 0 and 1, and since they are adjacent you take the larger. Writing dp[1] = nums[1] quietly assumes house 1 is robbed, which contradicts the sentence you wrote.

The two-variable collapse, since dp[i] reads only two cells back:

def rob(nums):
    prev2, prev1 = 0, 0                 # dp[i-2], dp[i-1]
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Simultaneous assignment matters. Written as two statements, prev2 = prev1 first destroys the value the second line needs. Python evaluates the entire right-hand tuple before binding anything, which is exactly what makes the one-liner correct.

This version needs no separate base-case branches: the initialization prev2 = prev1 = 0 encodes the empty-prefix base values and handles empty, single and double inputs uniformly. That is a genuine advantage of the rolling form and worth pointing out.

House Robber II — houses in a circle, so first and last are adjacent:

def rob_circular(nums):
    if len(nums) == 1:
        return nums[0]
 
    def rob_line(arr):
        prev2, prev1 = 0, 0
        for x in arr:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1
 
    return max(rob_line(nums[:-1]), rob_line(nums[1:]))

No new recurrence. The insight is that in any valid solution, house 0 and house n−1 cannot both be robbed. So either house 0 is excluded, or house n−1 is excluded — those two cases cover every possibility, possibly overlapping, and taking the max of two linear solves is correct. Overlap is fine because we are maximising, not counting.

Delete and Earn — same reduction, applied to values instead of positions:

from collections import Counter
 
def deleteAndEarn(nums):
    total = Counter()
    for x in nums:
        total[x] += x                   # all copies of x are taken together
    prev2 = prev1 = 0
    prev_val = None
    for v in sorted(total):
        take = total[v] + (prev1 if prev_val != v - 1 else prev2)
        prev2, prev1 = prev1, max(prev1, take)
        prev_val = v
    return prev1

The reduction: deleting v forces deletion of all v−1 and v+1, and you always take every copy of v at once since taking one costs you nothing extra. So build a value-indexed array where the "house value" is v × count(v), and adjacency in value space is exactly the House Robber adjacency constraint. Recognising this is the entire problem; the code after is copy-paste.

The cue

You are looking at 1D linear DP when the statement contains one of these tells:

1. "You cannot pick two adjacent X" — houses, elements, seats, days. Direct House Robber signal.
2. A choice at each index that only constrains a bounded number of neighbours. Cooldown periods, gaps, no-two-in-a-row.
3. "Maximum / minimum over a sequence" where a greedy sweep demonstrably fails. On [2, 3, 2], repeatedly taking the largest available house and blocking its neighbours takes only 3; the two endpoints give 4. This disproves that greedy rule, not every possible greedy algorithm.
4. A single index is enough to describe the state. If you need (i, j) or (i, capacity), you are in a later session. If i alone determines everything, it is 1D.
5. Constraints around n ≤ 10^5 with an exponential brute force. Linear DP is the natural fit for that gap.

The negative cue: if dp[i] needs to look at all previous indices — longest increasing subsequence, for instance — the recurrence is not bounded-window and belongs to session 36 at O(n²). The distinction is whether the window has a fixed size.

Guided solve

House Robber. An array where each element is the money in a house. Adjacent houses have connected alarms, so robbing two adjacent houses triggers it. Return the maximum you can rob.

Test a precisely specified greedy rule: repeatedly take the largest unblocked house and block its neighbours. On [2, 3, 2] it takes the middle 3 and blocks both endpoints, but taking the endpoints yields 4. By contrast, [2, 1, 1, 2] is not a counterexample: that greedy can take both endpoint 2s. A failed informal trace is not evidence against an algorithm.

Now the state sentence, written before any array:

dp[i] = the maximum amount I can rob from houses 0 through i inclusive, with no assumption about whether house i is robbed.

Now the transition, derived by case analysis on the last house:

• Rob house i. Then house i−1 is off limits. The best I could have done up to i−2 is dp[i-2], and that value has no assumption about house i−2, so adding nums[i] is legal. Total: dp[i-2] + nums[i].
• Skip house i. Then the answer is exactly the best over 0..i−1, which is dp[i-1].

These two cases are exhaustive — house i is either robbed or not — so dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Notice how the definition sentence made the derivation mechanical. The phrase "no assumption about whether house i is robbed" is precisely what licenses dp[i-2] + nums[i]. Under the alternative definition — "max assuming house i IS robbed" — that step would be invalid and the recurrence would be different.

Base cases, from the sentence. dp[0] = best over house 0 alone = nums[0]. dp[1] = best over houses 0 and 1, which are adjacent, so max(nums[0], nums[1]).

Trace on [2, 7, 9, 3, 1]. dp[0] = 2. dp[1] = max(2, 7) = 7. dp[2] = max(7, 2+9) = 11. dp[3] = max(11, 7+3) = 11. dp[4] = max(11, 11+1) = 12. Answer 12, matching 2 + 9 + 1.

For reconstruction, the two final scalars alone do not record the chosen houses. Keep the table for a linear-time backward walk (or accept recomputation with a value-only solver). If dp[i] == dp[i-1], skipping i is one optimal choice, not proof that every optimum skips it. Handle i = 0 explicitly rather than reading Python's dp[-1].

def robbed_indices(nums):
    # Nonnegative house values; return one optimal set of indices.
    dp = [0] * (len(nums) + 1)  # dp[k]: best from the first k houses
    for k, x in enumerate(nums, 1):
        dp[k] = max(dp[k - 1], (dp[k - 2] if k >= 2 else 0) + x)
    chosen = []
    k = len(nums)
    while k > 0:
        if dp[k] == dp[k - 1]:
            k -= 1
        else:
            chosen.append(k - 1)
            k -= 2
    return chosen[::-1]

On [2, 2], this tie rule returns [0]; [1] is also optimal. On [5], it returns [0] without accidentally comparing the first entry with the last.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• House Robber II — circular. Do not invent a circular recurrence. Ask what single fact about house 0 and house n−1 lets you split into two linear problems, and watch the n == 1 edge case.
• Delete and Earn — the reduction is the whole problem. Before writing DP, work out what array you would run House Robber on and why adjacency in that array means the right thing.

If both land early, do Best Time to Buy and Sell Stock. It is not strictly House Robber, but it is the cleanest example of a 1D sweep where the state is "best answer so far plus one running extremum", and it is a good contrast case.

Common failure modes

dp[1] = nums[1] instead of max(nums[0], nums[1]). Contradicts the state definition. Fails on [5, 1], where the answer is 5.

Assignment order in the rolling form. prev2 = prev1 then prev1 = max(...) destroys prev2's needed value before it is used. Use the simultaneous tuple form, or introduce a temp.

Wrapping the linear recurrence with modular indices. That loses the first/last exclusion constraint. The two-run reduction handles it directly; a state tracking whether the first house was taken is another valid approach.

Forgetting n == 1 in House Robber II. nums[:-1] and nums[1:] are both empty for a single-element input, so you return 0 instead of nums[0].

Confusing numeric adjacency with adjacency in the sorted key list. A dense array puts weight 0 at absent values, so the ordinary House Robber recurrence handles gaps without a special branch. The sparse sorted-key code above must instead check prev_val != v - 1; for [2, 4], both values may be taken, giving 6.

Never writing the state sentence. The meta-failure that causes most of the above. Two minutes of English saves twenty minutes of debugging a transition that was never wrong.

Myth: The hard part of a DP problem is finding the transition formula, so that is where I should spend my thinking time.

Why: The transition is a mechanical consequence of the state definition. Once you can state precisely what dp[i] means, the transition comes from case analysis on the last decision — a step that takes thirty seconds. The hard part is choosing a state that is both sufficient (it captures everything later decisions need to know) and minimal (it does not carry redundant information that blows up the state count). When people say a transition 'doesn't work', what is almost always true is that their state was underspecified — it did not carry enough information to make the decision. Debugging the formula cannot fix that.

Steps 1: Because every house is either robbed or not robbed, case analysis on the last house is exhaustive and mutually exclusive.

Steps 2: Because robbing house i forbids house i−1 but says nothing about houses 0 through i−2, the best completion of that case is exactly dp[i−2] plus nums[i].

Steps 3: Because skipping house i imposes no new constraint, the best completion of that case is exactly dp[i−1].

Steps 4: Because the two cases partition all possibilities, the maximum over them is the true maximum — this is the optimal substructure argument, stated explicitly.

Steps 5: Because dp[i] reads only dp[i−1] and dp[i−2], the array can be collapsed to two scalars without changing any computed value.

Steps 6: Therefore the testable prediction is that on nums = [2, 7, 9, 3, 1] the table fills as [2, 7, 11, 11, 12], and the rolling-variable version produces the identical final value of 12 while never allocating an array.

Picture: You walk down the street of houses carrying two numbers on a slip of paper: the best you could have done stopping at the previous house, and the best stopping at the one before that. At each house you compare skipping it against taking it plus the older number, keep the winner, and shift the slip along.

Trigger: Fires on 'cannot pick two adjacent' or any per-index choice whose only constraint reaches a fixed number of positions backwards.

Name: Full dp array

Gain: Readable and debuggable — you can print the table and check it by hand; supports a direct backward reconstruction of chosen items

Cost: O(n) space when O(1) is achievable

Name: Two rolling variables

Gain: O(1) space; encodes base values in the two-zero initialization rather than separate branches

Cost: Final scalars do not retain choices; reconstruction needs extra records or recomputation. Assignment order is a real trap; intermediate states are harder to inspect.

Name: Top-down memoised recursion

Gain: Transition mirrors the case analysis exactly, so it is the easiest form to derive under pressure

Cost: O(n) stack depth risks Python's recursion limit at n = 10^5, which is inside typical constraints for this family

Pick: Write the full array first and verify it against a hand-computed trace. Collapse to rolling variables only after it is correct and only when the problem asks for the value alone. Keep the array whenever the problem asks which items were selected, or when a follow-up seems likely to ask.

Complexity

Time: O(n). There are n states, one per index, and each transition is a single max of two terms, which is O(1). By the states-times-transition formula from session 33, that is O(n).

Space: O(n) for the array form, O(1) for the rolling form. Both compute identical values; the rolling form simply discards cells it will never read again.

House Robber II: O(n) time, O(n) auxiliary space as written. Two linear passes is still O(n) — the constant factor of 2 does not change the class. The slices nums[:-1] and nums[1:] do allocate O(n), so if you want genuine O(1) space, pass index ranges instead of slicing.

Delete and Earn: O(n + k log k) where k is the number of distinct values. Building the counter is O(n); sorting the distinct values is O(k log k); the DP sweep is O(k). If values are bounded by 10^4, you can index directly into an array of that size and drop the sort, giving O(n + V) where V is the value range.

Self-check (answer follows each question).

Q: State the definition of dp[i] in House Robber precisely enough to justify the transition.

A: dp[i] is the maximum amount robbable considering only houses 0 through i inclusive, with no assumption about whether house i itself is robbed. That last clause is what licenses using dp[i−2] + nums[i], since dp[i−2] makes no commitment about house i−2.

Q: Why is dp[1] = max(nums[0], nums[1]) and not nums[1]?

A: Under the stated definition dp[1] is the best over houses 0 and 1. They are adjacent so only one may be taken, and the best single choice is the larger of the two. Writing nums[1] smuggles in an assumption the definition does not make.

Q: How does House Robber II reduce to House Robber, and why is taking the max of the two runs valid?

A: Houses 0 and n−1 cannot both be robbed, so every valid solution excludes at least one of them. Run the linear solver on nums[:-1] and on nums[1:] and take the larger. The two cases overlap, but overlap is harmless when maximising rather than counting.

Q: Why use simultaneous assignment or a temporary in the rolling update?

A: prev2's new value is the old prev1, and prev1's new value also reads the old prev2. The naive sequential update prev2 = prev1 destroys that old prev2 before it is used. Python evaluates the right-hand tuple before binding the targets; a temporary preserving the old value is equally valid.

Q: What transformation turns Delete and Earn into House Robber?

A: Aggregate all copies of each value into a single weight v × count(v), then treat values as positions. Deleting v forbids v−1 and v+1, which is exactly the adjacency constraint of House Robber in value space rather than index space.

Q: You need to report WHICH houses were robbed, not just the total. What changes, and how do you recover the choice?

A: Keep the table for the direct backward walk shown in robbed_indices. At an equality, skipping is one optimal choice; otherwise take the house and jump over its neighbour. A prefix-length table makes the k = 0 boundary explicit. Decision records or recomputation are alternatives; the final two scalars alone are insufficient.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

House Robber enters the queue. When it comes back, the pass criterion is not the code — it is whether you wrote the state sentence first, unprompted. If you jumped straight to the array, log it warm even if the answer was right. The habit is the thing being trained.

• Write the state definition as an English sentence before any code. The transition is then a mechanical case analysis on the last decision.

• Most DP bugs are underspecified state, not a wrong formula. Debugging the transition cannot fix a state that carries too little information.

• House Robber: dp[i] = max(dp[i−1], dp[i−2] + nums[i]), with dp[1] = max(nums[0], nums[1]) — not nums[1].

• Circular variants reduce to linear ones by excluding one endpoint at a time. Two linear passes, take the max. Do not invent a circular recurrence.

• Delete and Earn is House Robber in value space. Recognising the reduction is the whole problem; the DP is copy-paste.

• Preserve old operands with simultaneous assignment or a temporary. Keep table/decision information for a direct witness reconstruction, or budget for recomputation.

Corrective source notes

• Python 3.14 assignment statements — the right-hand expression list is evaluated before its values are assigned to the targets. Freshly checked 2026-10-09.

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.