L34 · DP II — 1D Linear

Series: LeetCode — From Basics to Interview-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.

Notice this version needs no base cases at all — starting both at 0 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. Try greedy on [2, 1, 1, 2] — take the biggest first gives 2 + 1 = 3, but the answer is 4. Greedy failing on a tiny counterexample is a strong DP signal.
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.

Before any code, kill greedy explicitly. Take [2, 7, 9, 3, 1]. Greedy by largest value takes 9, which blocks 7 and 3, then takes 2 and 1, for 12. The correct answer is 2 + 9 + 1 = 12 as well — so that example does not distinguish them. Try [2, 1, 1, 2]: greedy takes a 2, blocks its neighbour, takes the other 2, giving 4, which is right. Try [1, 3, 1, 3, 100]: greedy takes 100, blocks the 3 before it, takes the remaining 3 and 1, giving 104. Correct is 3 + 3 + 100 = wait — 3 at index 1 and 3 at index 3 are not adjacent, and 100 at index 4 is adjacent to index 3. So 3 + 100 = 103, or 1 + 1 + 100 = 102, or 3 + 3 = 6. Best with 100 is index 1 plus index 4: 103. Greedy's 104 is not achievable. The point of this exercise is not any single counterexample — it is that you cannot reason about greedy here without care, which is itself the signal.

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.

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.

Solving House Robber II with a modular-arithmetic circular recurrence. It does not work — the constraint couples the first and last decisions in a way a left-to-right sweep cannot express. Split into two linear problems instead.

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].

In Delete and Earn, iterating over values that are absent. If you sweep range(max(nums)+1) you must handle gaps, where the previous value is not v−1 and there is no adjacency constraint. If you sweep only present values sorted, you must check prev_val != v - 1 explicitly. Either works; mixing them does not.

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.

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(1) space. 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.

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.