1D DP: derive the state before compressing it

Reader guide and study workflow · Complete course map

A DP state is a precise question about a smaller input. A recurrence must explain every possible final decision, show that its alternatives cover all valid solutions, and specify which earlier answers are needed. Rolling variables come only after that dependency is clear.

A common derivation protocol

Write five things: the state meaning, the final decision, the recurrence, the base cases, and a dependency-respecting iteration order. Then prove two directions: every candidate generated by the recurrence is feasible, and every optimal or counted solution is represented by some candidate. This prevents a recurrence that looks plausible but silently misses a case.

Counting: disjoint final choices

For stair routes, F(i)=F(i-1)+F(i-2): the final move is either one or two steps. For digit decodings, the same two predecessor distances occur, but each transition has a different validity guard. A nonzero last digit admits D(i-1); a last pair from 10 through 26 admits D(i-2). A zero is not a valid standalone code.

The abstract empty-prefix count is one because there is one way to choose no moves or codes. That mathematical base does not automatically change the public API: ClimbStairs(0) and NumDecodings("") currently return zero outside or at their documented boundary behavior. Keep the internal state interpretation distinct from the external function convention.

Optimization: exhaustive alternatives, not local preference

For linear robbery, R(i)=max(R(i-1),R(i-2)+value[i-1]). The final house is either skipped or taken. The circle adds only an endpoint conflict: for n>=2, solve once without the first house and once without the last, then take the larger result. Handle the singleton separately.

For maximum subarray, the state must end exactly at i: E(i)=max(value[i],E(i-1)+value[i]). Another variable remembers the best endpoint seen. For maximum product, keep both minimum and maximum ending products because multiplying by a negative reverses their order. Nonempty problems initialize from the first value, not an artificial zero candidate.

The mathematical maximum does not require evaluating both branches in machine arithmetic. If the previous ending sum is negative, choose the singleton value[i] before adding. For [MinInt,-1], the correct answer is -1, but eagerly computing MinInt + (-1) overflows even though that branch cannot win. The reference resets on a negative preceding sum and adds only when extending can help. Bounds on retained answers alone do not justify evaluating a discarded candidate.

Prefix reachability and minimum counts

Word Break views boundaries 0..n as vertices. A dictionary word s[j:i] connects j to i. Reachability obeys:

dp[0] = true
for i = 1..n:
    for j = max(0, i-maxWordLength)..i-1:
        if dp[j] and s[j:i] is in dictionary:
            dp[i] = true
            break

Coin Change instead minimizes the number of positive-denomination edges needed to reach an amount:

dp[0] = 0
all other dp entries = amount+1
for a = 1..amount:
    for each positive coin c:
        if c <= a:
            dp[a] = min(dp[a], dp[a-c]+1)

The positivity and indexing guards are part of the algorithm. Negative coins do not preserve the smaller-amount dependency, and c>a would access a negative index. Reusing a denomination is allowed because predecessors can themselves use that denomination.

Dominance compression: longest increasing subsequence

The quadratic model asks for the best increasing subsequence ending at each index. A stronger summary keeps the minimum possible last value for each achievable length. Smaller tails dominate larger tails for future extension. Find the first tail >=x and replace it; append only when every existing tail is smaller. Equality must replace, not extend, because the subsequence is strictly increasing.

Each tail can come from a different witness subsequence. The tails array is a length certificate, not necessarily one actual subsequence. Returning a witness would require additional predecessor and endpoint information beyond the preserved length-only API.

Prerequisites and readiness

Be comfortable with prefix indices, contiguous subarrays versus subsequences, induction, and binary-search boundaries. Explain what the empty prefix contributes before introducing a recurrence or an infinity sentinel.

For a first pass, derive Climbing Stairs and House Robber with a full prefix table, then compress House Robber using the trace below. Next separate an ending-at-this-position state from a global answer with Maximum Subarray and Maximum Product. Word Break and Coin Change introduce reachability and unreachable states; LIS then asks which states can be safely discarded. You can open any problem directly; this order is guidance for building the dependencies.

Reasoning workshop: trace dependencies before overwriting them

Worked example: two prefix answers, then one new answer

For robbery [2,7,9,3,1], prev1 is the optimum for all houses already read and prev2 is the optimum before the last of those houses. Both start at zero. Compute both alternatives from the old state before shifting it:

New house	Old prev2	Old prev1 / skip	Take = old prev2 + value	New optimum
2	0	0	2	2
7	0	2	7	7
9	2	7	11	11
3	7	11	10	11
1	11	11	12	12

After a row, shift prev2 to the old prev1, then prev1 to the new optimum. The two old 11s in the last row represent different prefixes even though their values match. The base covers the empty prefix; the take/skip split covers every legal choice for the new house; the shift preserves the two prefix meanings. When all houses have been read, prev1 is therefore the requested full-prefix optimum.

Finish the trace before revealing the answer

For [4,1,2,7], the first two prefix optima are 4,4. Before processing 2, the state is (prev2,prev1)=(4,4). Fill the remaining two rows as (skip,take,new optimum) and write the final pair of rolling states. Then diagnose this proposed update order:

prev2 = prev1
cur = max(prev1, prev2 + value)
prev1 = cur

What is the first incorrect result on [4,1]?

Model answer: preserve the old two-back prefix

The remaining rows are (4,6,6) and (6,11,11). After the last shift the pair is (6,11); houses at indices 0 and 3 achieve 11.

The proposed code overwrites prev2 too early. On the second house of [4,1] it computes 4+1=5, combining adjacent houses. The correct answer is 4. Compute cur before either assignment, or use a simultaneous assignment whose right-hand expressions all read the old states.

Ending here versus best anywhere

For maximum product [-2,3,-4], ending extrema are (-2,-2), (3,-6), and (24,-12), written as (maximum,minimum). The -6 state is indispensable: it becomes 24. A zero resets both ending extrema to zero, but the global best must not be reset with them.

Competing prefixes and dominated states

For Word Break, "cars" with ["car","ca","rs"] defeats longest-prefix greediness. Boundary 3 is reachable but leads nowhere; boundary 2 reaches the end through "rs". For Coin Change [1,3,4], amount 6 similarly defeats largest-coin greediness: 4+1+1 uses three coins while 3+3 uses two. These failures identify what future information a greedy choice throws away.

For LIS [2,6,8,3,4,5,1], tails evolve to [1,3,4,5], of length four. Those values do not form a subsequence because 1 appears last. To reconstruct the length-only algorithm, prove why the smallest tail for a fixed length is never worse for any future extension.

Guarded counting transitions

For decoding "101", the one-digit zero transition is forbidden, but the pair "10" is valid; then the final "1" extends it. For "100", neither a last zero nor "00" is valid, so the count becomes zero. Test guards independently instead of treating zero as a whole-input shortcut.

Cost and representability are part of the state contract

The supplied Word Break uses hash lookups on candidate substrings. A slice header is constant size, but hashing its bytes is not free: the worst-case expected byte work is O(D+nL²), not simply O(nL), for total dictionary bytes D and maximum relevant word length L. LIS is O(n log n), while the rolling sum/count recurrences are linear.

Machine integers do not hold arbitrary mathematical counts. The problem constraints specify which arithmetic must fit int: every decoded-prefix count, every contiguous subarray product for Maximum Product, and the optimal nonnegative robbery total. For decoding, a small final answer is insufficient: a long run of ones followed by 00 can have enormous intermediate counts yet finish at zero. For products, the negative minimum must fit too because it can become the next positive maximum.

Maximum Subarray instead guarantees that the mathematical maximum fits; the safe reset-before-add order above avoids computing discarded sums below MinInt. ClimbStairs has a simpler numeric bound: n<=45 keeps its answer within signed 32 bits. These are input-domain conditions, not requests for saturation, modular answers, or a changed return type.

Reconstruction lab and answer key

Climbing Stairs

List the five ordered routes for n=4. Why are 1,2,1 and 2,1,1 different routes?

Model answer

The routes are 1,1,1,1; 1,1,2; 1,2,1; 2,1,1; and 2,2. Order describes when each step is taken, so the two named sequences are distinct.

House Robber

For [3,2,5,10,7], reconstruct the prefix optima without looking at the worked trace. Which indices attain the answer?

Model answer

The prefix optima are 3,3,8,13,15. Indices 0,2,4 contribute 3+5+7=15. The last decision compares skip 13 with take 8+7; using the immediately preceding prefix 13 in the take branch would combine adjacent houses.

House Robber II

Why does [2,3,2] yield 3 instead of 4? Why is a singleton [7] not reduced to an empty line?

Model answer

The two 2s are adjacent across the circular boundary, so cannot both be selected. The two linear optima are each 3. A singleton has one house and no distinct neighboring house; its value 7 is available.

Maximum Subarray

For [-5,-2,-8], what is the answer and why is initializing the answer to zero incorrect?

Model answer

The answer is -2, the singleton middle element. Zero represents an empty subarray, which is not an allowed candidate.

Maximum Product Subarray

For [-2,4,-3], the first two values leave (oldMax,oldMin)=(4,-8). Compute the three candidates for the next value. A buggy direct recurrence writes maxEnding first, then uses that new value to compute minEnding. Which impossible minimum can it produce?

Model answer

The candidates are -3, 4*(-3)=-12, and (-8)*(-3)=24, giving (maxEnding,minEnding)=(24,-12). Reading the new maximum 24 in the minimum calculation introduces 24*(-3)=-72, multiplying by the current element a second time. Save both old extrema before the direct recurrence. The reference instead swaps extrema when the next value is negative, then updates each from its own previous value.

Word Break

For s="aaaa" and dictionary ["a","aa"], the boolean API returns true. Suppose the requested output changes to the number of ordered dictionary-word segmentations. Which DP quantity changes, why can the inner loop no longer stop on its first successful predecessor, and what is the answer? Treat dictionary entries as a set.

Model answer

Replace reachability with the number of segmentations of each prefix. The empty-prefix count is 1. At each endpoint, add the count at every predecessor whose final substring is a dictionary word; breaking on the first one loses other disjoint final-word choices. Prefix counts for lengths 0..4 are [1,1,2,3,5]. The five segmentations are a|a|a|a, aa|a|a, a|aa|a, a|a|aa, and aa|aa. A duplicate dictionary entry must not duplicate an identical segmentation. This transfer changes the result contract; the provided WordBreak function remains boolean.

Coin Change

With coins [2,3], complete the minimum-count table for amounts 0..7. Use unreachable where needed. Then change the task: each listed coin may be used at most once. Why would the existing recurrence give a wrong answer for coins [3], amount 6?

Model answer

The table is [0,unreachable,1,1,2,2,2,3]; amount 7 can use 2+2+3. Only amount zero starts with count zero. Initializing every amount to zero would invent reachable predecessors.

For coins [3], the existing unbounded recurrence reaches 3 and then reuses that state to reach 6 with two coins. Under the changed rule, 6 is unreachable. Track which coin entries have been considered; a compressed version processes each coin once and amounts downward so the same coin cannot feed its own next update. This is a transfer exercise, not a change to the pack’s unlimited-reuse contract.

Longest Increasing Subsequence

Process [3,5,6,1,2,4] with tails. Give its final array and length. Which length-three witness does it certify, and why can the old ending value 6 be discarded when 4 arrives?

Model answer

The final tails are [1,2,4], with length three and witness 1,2,4. The old length-three ending 6 is no better for any future strictly larger extension: every future value able to follow 6 can also follow 4, while values between 4 and 6 can follow only 4. Replacing that endpoint preserves achievable length and improves future options.

Decode Ways

Compute the counts for 1120 and 2101 by separating the final one-digit and two-digit transitions. A shortcut rejects every string containing zero: which valid final choices does that throw away?

Model answer

1120 has two decodings: 1|1|20 and 11|20. Its final zero forbids the one-digit transition but the pair 20 inherits both decodings of prefix 11. For 2101, only 2|10|1 works: 01 is invalid, so the final 1 extends the single valid decoding of 210. Zero is allowed inside 10 or 20; it is the individual transition, not the whole string, that must be guarded.

Problems in this module

• Climbing Stairs
• House Robber
• House Robber II
• Maximum Subarray
• Maximum Product Subarray
• Word Break
• Coin Change
• Longest Increasing Subsequence
• Decode Ways

Interactive checkpoint

Open the 1D DP (Including Kadane) quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

1D DP (Including Kadane)

Pattern A: Linear recurrence (Fibonacci-like)

Pattern B: Take/skip maximization

Pattern C: Subarray DP (Kadane / sign-aware)

Pattern D: Prefix DP (segmentation / coin / decode)

Pattern E: LIS via tails (DP + binary search)

When to use 1D DP (checklist)

Common failures (checklist)

Why these problems fit

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable