1D DP (Including Kadane) — choose the invariant

For [2,7,9,3,1], what must a state remember to decide whether to take the final house?

Name a subproblem, not a variable.

1 / 13

Climbing Stairs — predict before coding

Partition routes by their final move. A route ending in one step comes from n-1; one ending in two steps comes from n-2. These alternatives are disjoint and exhaustive.

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

Presenter notes

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.

Correctness argument: Let F(i) count ordered sequences of ones and twos summing to i. Removing the final one-step move is a bijection with routes to i-1; removing a final two-step move is a bijection with routes to i-2. No route belongs to both classes, so F(i)=F(i-1)+F(i-2). The bases F(1)=1 and F(2)=2 are direct enumerations. Before computing i, the rolling variables hold exactly these preceding counts; assigning their sum and shifting preserves the invariant. Thus the returned value is F(n). The stated n<=45 bound fits a signed 32-bit int.

Debugging prompt: Check n=1 and n=2 before the loop. Preserve both old counts until the new count is formed. The mathematical empty-route base F(0)=1 is useful for derivation, but the existing API returns 0 for n=0, outside its stated positive-n domain.

2 / 13

Worked trace — compute before shifting

House values [2,7,9,3,1]; both prefix states begin at 0.

Value	Old two-back	Old one-back	Take	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

3 / 13

Faded trace — finish, then diagnose

House values [4,1,2,7]; first two prefix optima: 4,4.

Before value 2: (two-back,one-back)=(4,4).

Complete the remaining (skip,take,new optimum) rows.

What fails if two-back = one-back executes before computing take?

4 / 13

House Robber — predict before coding

The final house is either skipped or taken. Taking it forbids exactly the previous house, so only two optimal prefix values are needed—not a remembered list of greedy choices.

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

Presenter notes

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.

Correctness argument: For the first i houses, let R(i) be the maximum total from a nonadjacent subset, allowing the empty subset. Every feasible subset either omits house i-1, bounded by R(i-1), or includes it, leaving an optimal subset of the first i-2 houses worth R(i-2)+value. Both alternatives are feasible, so their maximum is exactly R(i). Empty-prefix bases are zero. Before each iteration, prev1 and prev2 store the preceding two optimal prefix values; computing before shifting preserves them. Induction yields the optimum for the full line.

Debugging prompt: Test empty, one-house, all-zero, and alternating high-value inputs. Do not overwrite the two-back state before computing take. Accumulated sums must fit int; a length bound alone does not guarantee that.

5 / 13

House Robber II — predict before coding

The extra circular edge only forbids choosing both endpoints. Every valid selection therefore belongs to at least one of two linear problems: exclude the first or exclude the last.

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

Presenter notes

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.

Correctness argument: For n>=2, a feasible circular selection cannot contain both indices 0 and n-1. If it omits the last, it is feasible in nums[:n-1]; if it omits the first, it is feasible in nums[1:]. Conversely every nonadjacent selection in either linear slice is valid on the circle because one endpoint is absent. The union of these two feasible families contains exactly all circular solutions, so the larger linear optimum is the circular optimum. Empty and singleton inputs require explicit handling: slicing away either endpoint of a singleton would incorrectly discard its only value.

Debugging prompt: Test lengths 0,1,2 separately and a case whose best line solution uses both endpoints. Use nonnegative amounts, as intended by the existing single-house behavior, and keep totals representable.

6 / 13

Maximum Subarray — predict before coding

The useful state is the best nonempty subarray ending exactly here, not the best subarray anywhere. A negative preceding sum can only hurt a segment that includes the current value.

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

Presenter notes

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

Correctness argument: Every nonempty subarray ending at index i is either the singleton nums[i] or an extension of a subarray ending at i-1. Among extensions, the previous maximum ending sum gives the largest total because the same nums[i] is added to every candidate. Thus E(i)=max(nums[i],E(i-1)+nums[i]). A separate best value takes the maximum of E over all processed endpoints, covering every possible nonempty subarray. Initializing both states from nums[0], rather than zero, preserves the required nonempty choice when all values are negative.

Debugging prompt: Test all-negative inputs, one value, zeros, and a reset after a large negative value. The recurrence is about subarrays, not arbitrary subsequences. The formula max(x,previous+x) is mathematical: if previous is negative, choose x before adding. On [MinInt,-1], eagerly computing the losing sum overflows although the correct answer -1 is representable. The reference branches before adding; retained sums still must fit int.

7 / 13

Maximum Product Subarray — predict before coding

Multiplication can reverse ordering: a very negative product becomes very positive after another negative factor. Retain both extreme products ending at the previous index.

Decision: 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?

Presenter notes

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.

Correctness argument: For a new value x, every nonempty subarray ending here is the singleton x or an extension of a prior ending subarray. Multiplication by positive x preserves order, by negative x reverses it, and by zero collapses all products to zero. Consequently the new maximum and minimum are the extrema of x, oldMaxx, and oldMinx. Swapping old extremes when x<0 lets the implementation compute these extrema with two comparisons while preserving both old values. The global answer is the maximum ending product over all endpoints. This argument assumes the products used in comparisons are representable; machine overflow would invalidate ordering.

Debugging prompt: Test zero-separated runs, an odd and even number of negatives, and single negative values. Initialize from the first element, not zero. All tracked intermediate products—not only the final answer—must fit int.

8 / 13

Word Break — predict before coding

A dictionary word is an edge between two prefix boundaries. The task is reachability from boundary 0 to boundary len(s), not greedy longest-word selection.

Decision: For s="aaaa" and dictionary ["a","aa"], change the output from existence to the number of segmentations. What state replaces a boolean, why must the predecessor loop keep going, and what is the result?

Presenter notes

Model answer: Store a count for each prefix, with empty-prefix count 1. Sum every valid final-word predecessor rather than stopping at the first. The 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. Treat dictionary entries as a set; duplicate entries do not create new segmentations. This is a changed-output exercise, while the actual API stays boolean.

Correctness argument: Let dp[i] mean that exactly s[:i] can be segmented into dictionary words. The empty prefix is reachable by taking no words. Any nonempty valid segmentation has a final word s[j:i] and a segmentable preceding prefix, so it implies dp[j] and dictionary membership. Conversely those two facts concatenate into a valid segmentation of s[:i]. Testing all j within the maximum dictionary word length is exhaustive because longer suffixes cannot be words. Induction in increasing i computes reachability at every boundary and hence the answer.

Debugging prompt: Test empty input, reusable words, a segmentable prefix with an impossible final byte, and overlapping dictionary prefixes. String slicing is cheap, but hashing a newly queried substring still reads its bytes.

9 / 13

Coin Change — predict before coding

Amounts form a directed acyclic graph when every coin is positive: taking a coin moves from a smaller amount to a larger one. The desired value is a shortest path measured in coin count.

Decision: 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?

Presenter notes

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.

Correctness argument: Let C(a) be the minimum number of coins totaling amount a, or unreachable. C(0)=0. Every nonempty solution for a has some last denomination c<=a and a solution for a-c; replacing that prefix with its optimum cannot worsen the count. Conversely adding c to any reachable a-c makes a feasible solution. Therefore C(a)=min(C(a-c)+1) over eligible denominations. Positive coins ensure predecessors are strictly smaller and already computed in increasing amount order. The sentinel amount+1 exceeds every possible feasible minimum because positive integer coins require at most amount coins.

Debugging prompt: Test amount zero, unreachable residues, duplicate denominations, and coins larger than the amount. Only positive denominations satisfy the recurrence and indexing contract. Never read dp[a-c] when c>a.

10 / 13

Longest Increasing Subsequence — predict before coding

For a fixed subsequence length, only its smallest achievable ending value matters for future extensions. This dominance rule compresses quadratic endpoint DP into a sorted array of tails.

Decision: 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?

Presenter notes

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.

Correctness argument: After a prefix, tails[k] is the smallest possible last value of any strictly increasing subsequence of length k+1 in that prefix. The tails are strictly increasing. For x, the first tail >=x identifies the longest shorter subsequence that can be extended by x; replacing that tail with x improves or preserves the best endpoint without reducing any achievable length. If no such tail exists, x extends the longest known subsequence and appends one length. Later positions cannot use x to create an even longer subsequence because their required predecessor tail is already >=x. Thus the number of tails is exactly the optimal length.

Debugging prompt: Use the first tail >=x for a strictly increasing sequence; using >x incorrectly counts equal values. Test all-equal and decreasing arrays. Reconstructing the actual subsequence needs predecessor/index state beyond this length-only API.

11 / 13

Decode Ways — predict before coding

Every valid decoding ends in either one valid nonzero digit or one valid two-digit number from 10 through 26. Zero cannot form a letter by itself.

Decision: 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?

Presenter notes

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.

Correctness argument: Let D(i) count decodings of the first i digits. A decoding ending in a one-digit code exists exactly when the last digit is 1..9 and contributes D(i-1). A decoding ending in a two-digit code exists exactly when that pair is 10..26 and contributes D(i-2). These final-code lengths give disjoint classes covering every decoding. D(0)=1 supplies the one empty prefix needed when consuming an initial pair, and D(1) is one only for a nonzero first digit. The rolling variables retain the preceding two counts before each update. The API separately returns zero for an empty input.

Debugging prompt: Test leading zeroes, consecutive zeroes, 10/20 versus 30, and a long run of ones. The stated 100000-digit maximum does not imply its count fits int; all rolling counts must be representable.

12 / 13

Reconstruct and transfer

Derive the full state, then compress it.

Check disjoint counting choices, exhaustive optimization choices, byte-level costs, and integer range.

13 / 13