On this page

DP Debugging & How to Find the State

There are two ways to be stuck on a dynamic-programming problem. The first is before any code exists: you can tell the problem "smells like DP", but you cannot say what dp[i] should mean. The second is after the code exists: it passes the sample, fails on submission, and the table is a wall of numbers you cannot interpret. This lesson is a toolkit for both.

For the first, you get a state-finding checklist, a procedure that starts from a brute-force recursion and reads the state off its parameters, and a dimension audit that tells you whether your state has too little or too much in it. For the second, you get a bug catalogue — each common DP bug with its symptom, a minimal input that exposes it, and the fix — plus two habits that find almost everything else: print the table, and stress-test the DP against a brute force on thousands of tiny random inputs. The lesson ends with eight worked examples that go from "stuck" to "state found".

The lesson sits near the end of Module 6 because it draws examples from every family, but it is written so you can read it right after DP Foundations and come back whenever you are stuck. It applies the general testing method of Testing & Debugging Algorithms to DP specifically.

Why it exists

DP bugs are unusually hard to find by reading code. A DP program is short — often ten lines — and every line looks plausible. The bug is usually not in a line at all; it is in the meaning of the table: the state forgot something the future needs, a base case encodes the wrong convention, or the loop visits cells in an order the recurrence does not allow. The program then produces numbers that are wrong but reasonable-looking, often correct on the sample and on most small cases. Reading the code again does not help, because the code faithfully implements a wrong idea.

Two facts make DP bugs findable anyway:

  1. Almost every DP has a trivially correct brute force — try every subset, every path, every split — that is exponentially slow but fine for inputs of size 5. Comparing the DP against it on thousands of random tiny inputs finds wrong answers in seconds and hands you the smallest failing input.
  2. A DP's state is a claim you can check by hand. "dp[i][c] = best value using the first i items with capacity c" is a sentence. Print the table for a three-item input and check three cells against the sentence. The first cell that disagrees points at the bug.

Competitive programmers have relied on the first fact for decades (they call it "stress testing"), and industry calls the same idea differential testing (McKeeman, 1998). The second is just the scientific method applied to a table.

Pattern triggers

Symptoms you observe, and the first thing to suspect.

If you see…Think of…
You cannot write "dp[…] = …" as one full English sentenceThe state is not defined yet; run the checklist
Correct on the samples, wrong on hidden testsStress test against brute force; the first failing input is usually tiny
Answer too large in a "use each item once" problemItems reused: one-row 0/1 knapsack looping capacity upward
Every count is 0Counting base case set to 0 instead of 1 ("one way to do nothing")
Answer off by exactly one step, one item or one characterOff-by-one between the state's index convention and the loops
A big negative number, or a huge positive one, in Java/C++Overflow: INF + 1, 32-bit counts, product before modulo
A negative number after % MOD (Java, C++, TypeScript)Subtraction under a modulus; fix with ((x % m) + m) % m
"Impossible" states win a maxUnreachable states initialised to 0 instead of
Some cells of the table are still 0 when you print itIteration order reads cells before they are filled
Works for , crashes for with no wrong answerRecursion depth (memoization); tabulate
Second test case gives a wrong answer, first is fineMemo or table not reset between test cases
Count is too large, by a factor that looks like a factorialCounting orderings instead of sets (loop order), or overlapping cases
Your DP is correct but too slowDimension audit: a dimension may be derivable from the others, or a transition can be sped up

Intuition & first principles

The state is a summary of the past

Think of solving the problem as making decisions one after another: take this item or not, step 1 or 2, cut here or there. At any moment you have a history — the decisions made so far. A state is a summary of that history, small enough to tabulate.

The single requirement on that summary:

Two histories that lead to the same state must have exactly the same possible futures, with the same value.

If that holds, you can throw the history away and keep only the best (or the count) per state. That property is called the Markov property in probability, and it is precisely what "optimal substructure" means operationally. If it fails — two histories with the same state differ in what they may do next — the DP will combine incompatible things, and you get wrong answers.

Example. House robber: you may not rob two adjacent houses. Suppose the state is just "I have decided houses ". Two histories — "robbed house " and "skipped house " — have different futures: one may rob house , the other may not. So "position" alone is not a valid state. Add one bit ("did I rob house ?") and the futures agree. (Or redefine the state as "best for the first houses", which handles the bit inside the transition — worked example 1.)

What to remember is decided by the future

That gives the central question for finding a state:

What do I need to know about the past to make the remaining decisions correctly?

Not "what happened", not "what would be nice to know" — only what the rules of the future depend on. In knapsack the future cares how much capacity is left and which items remain, not which items you took. In LIS it cares about the last value taken. In a "no two adjacent" rule it cares about the previous choice. In a "use each worker once" rule it cares about the set of used workers. Each of those is a dimension.

Too little and too much

  • Too little in the state: two histories share a state but have different futures. Symptom: wrong answers. Fix: add the missing fact.
  • Too much in the state: two states always have the same future but are kept apart. Symptom: correct but slow (or out of memory). Fix: drop the redundant fact, or merge states.

The dimension audit is a structured way to check both.

The state-finding checklist

Work through these in order with pen and paper. Most problems yield by question 5.

  1. What are the decisions, and in what order can I make them? Item by item, position by position, day by day, cut by cut. If there is no natural order, try sorting the input (by deadline, by end time, by size) — sorting often creates one.
  2. What does a complete solution look like as a sequence of decisions? Write one on a small example. "Take items 2 and 4." "Rob houses 0, 2, 4." "Buy day 0, sell day 2, rest day 3, buy day 3…"
  3. What changes between subproblems? Usually a position or a pair of positions (prefix length, interval ends, a tree node) plus a resource (capacity, remaining budget, number of moves left).
  4. What do I need to know about the past to make the next decision legally? Constraints that mention the previous choice ("no two adjacent", "cooldown", "different colour from the neighbour") need the previous choice in the state. Constraints on totals need the running total (or the remaining budget).
  5. What do I need to know to evaluate the objective from here on? If the score of a future decision depends on something past (the last value, the current height, the current multiplier), that something goes into the state.
  6. Can I make the state smaller? Anchoring at the end ("ending at "), using "remaining" instead of "used", or choosing a different decision order (which element is last rather than first) often removes a dimension.
  7. Count the states and the transitions. Product within budget (roughly simple steps for C++/Java per second, for Python)? If not, go back to 6.
  8. Write the state as one sentence, including "exactly" versus "at most", "prefix" versus "suffix", and whether the boundary element is included.

Two moves deserve special mention because they unlock problems that otherwise look impossible:

  • "Ending at" instead of "within". LIS, maximum subarray, longest palindrome ending here. When the transition needs to know the last element, make the last element part of the state by definition, then take the answer as a max over all endings.
  • "Last" instead of "first". In interval problems (burst balloons, matrix chain) the first operation splits the problem into pieces that still interact; the last one splits it into pieces that do not. Worked example 5.

Mechanics: from brute force to a DP you trust

The reliable workflow is four steps, and the first is the one people skip.

flowchart TD
    BF["1. Brute-force recursion<br/>parameters = what changes"] --> MEMO["2. Memoize on those parameters"]
    MEMO --> AUD["3. Dimension audit<br/>necessary? sufficient? size?"]
    AUD --> TAB["4. Tabulate in a valid order<br/>roll arrays if needed"]
    TAB --> ST["Stress test vs step 1<br/>on tiny random inputs"]
    ST -->|"mismatch"| PR["Print the table for the<br/>smallest failing input"]
    PR --> FIX["Find the first wrong cell<br/>fix state, base or order"]
    FIX --> ST
    ST -->|"all pass"| DONE["Submit / ship"]

Step 1: write the brute-force recursion first

Write a recursive function that makes the decisions one at a time and tries every option. Pass along, as parameters, whatever the remaining decisions need — this is the checklist's question 4 answered in code. Do not optimise anything yet.

House robber, brute force:

def rob_brute(a, i=0):
    """Best money from houses i, i+1, ... (house i is allowed)."""
    if i >= len(a):
        return 0
    skip = rob_brute(a, i + 1)
    take = a[i] + rob_brute(a, i + 2)    # taking i forbids i + 1, so jump to i + 2
    return max(skip, take)

The function's parameters (other than the fixed input a) are just i. That is the state. The recursion is the transition, the if is the base case, rob_brute(a, 0) is the answer. On 20 houses it makes 35,421 calls for 21 distinct values of i — overlapping subproblems, visible by counting.

Two rules make this step productive:

  • Parameters must be the minimum the future needs, not the whole history. If you find yourself passing a list of chosen items, ask what the future actually looks at — a count, a sum, a last element, a set of at most 20 things (bitmask).
  • No global mutable state. A brute force that appends to a shared list or flips a global flag cannot be memoized. Everything the function depends on must be a parameter or the read-only input.

Step 2: memoize

Add a cache keyed on the parameters. If the function is pure (same parameters, same result), memoization cannot change its answers — only its speed. That is why the brute force is such a good starting point: the memoized version is correct by construction if the brute force was.

Step 3: the dimension audit

For each parameter of the state, ask four questions.

QuestionIf the answer is no…
Necessary? Do two states that differ only in this parameter ever have different futures?Drop it: it multiplies the table for nothing
Derivable? Can it be computed from the other parameters?Drop it and compute it when needed
Sufficient? With all parameters fixed, is the future fully determined by the remaining input?Something is missing: wrong answers ahead
Bounded? How many values can it take?Multiply all ranges: that is the table size

Then multiply: states × transitions per state.

Audits on familiar problems:

ProblemFirst stateAudit findingFinal stateSize
Cherry pickup (two walkers on an grid), where = steps taken: two dimensions derivable instead of — see Grid & Path DP
0/1 knapsack(capacity left)Not sufficient: does not say which items remain(item index, capacity left)
Bitmask assignment ( workers to jobs)(worker index, set of used jobs)Worker index = number of used jobs (popcount): derivable(set of used jobs) states, time
LIS(position, last value taken)Last value can be any of input values: states, fine but clumsy"ending at ": the last value is states, time
Stock with cooldown(day)Not sufficient: the future depends on holding a share and on whether you just sold(day, hold / just sold / free)
Edit distance(i, j, ops used so far)"ops used" is the value, not part of the state(i, j)

The last row is a common beginner mistake: putting the quantity being optimised into the state. The thing you minimise or count is the value stored in the cell, not an index of the table. (Exception: when the constraint is on one quantity and the objective is another — then the constrained one is a dimension, as capacity is in knapsack.)

Step 4: tabulate in a valid order

Arrows in the memoized recursion go from a state to the states it calls. Tabulation must compute every state after all the states it calls. Read the order off the transition:

  • Reads , → increasing .
  • Reads → rows in increasing , any column order unless the same row is also read.
  • Reads , , (intervals) → decreasing , increasing ; or by increasing length .
  • Reads a smaller subset (bitmask) → increasing mask value works, because a submask is numerically smaller.
  • Reads children (trees) → post-order.

If in doubt, keep the memoized version — it finds the order itself.

Trace: the stress test catches the classic knapsack bug

The implementation below compares two one-row 0/1 knapsack DPs with a brute force that tries all subsets. One DP loops capacity downward (correct); the "buggy" one loops upward, which lets an item be used again. Inputs are generated smallest first (one item for the first 50 trials, then two items, and so on up to six) from a fixed seed, so the run is reproducible — the random generator is the same in all four languages, and all four print the same counterexample.

The first eight trials (weights, values, capacity → answers):

TrialItems (weight:value)CapacityBrute forceDP (downward)DP (upward, buggy)Buggy verdict
02:656612FAIL
11:989972fail
21:13113fail
35:14000ok
45:56555ok
53:310339fail
62:50000ok
75:53000ok

The harness stops at the first failure — trial 0, a single item. Over all 300 trials the buggy version is wrong 169 times; the correct one never. The counterexample tells the whole story: one item of weight 2 and value 6, capacity 5, and the buggy DP reports 12 = 6 + 6. Printing its table for that input (next section) shows exactly where the item gets counted twice.

Note what the bug is not caught by: trials 3, 4, 6 and 7 pass, because the item does not fit twice. A hand-written test suite that happened to contain only those shapes would pass. Random inputs do not care what you expected.

Printing the table

When a stress test hands you a failing input, print the table for it and check cells against the state sentence, starting from the base cases. The first wrong cell localises the bug: if its inputs are right and it is wrong, the transition is wrong; if its inputs are wrong, go to them.

A small helper is worth keeping in your template:

def print_table(dp, row_labels=None, col_labels=None, width=4):
    """Pretty-print a 1-D or 2-D DP table with labels; INF shown as '∞'."""
    rows = dp if isinstance(dp[0], list) else [dp]
    fmt = lambda x: "∞" if x == float("inf") else ("-∞" if x == float("-inf") else str(x))
    if col_labels is not None:
        print(" " * width + "".join(str(c).rjust(width) for c in col_labels))
    for r, row in enumerate(rows):
        label = str(row_labels[r]) if row_labels else ""
        print(label.rjust(width) + "".join(fmt(x).rjust(width) for x in row))

Knapsack, one item (weight 2, value 6), capacity 0..5, snapshot of the row after each item:

correct (capacity loop downward)        buggy (capacity loop upward)
           0     1     2     3     4     5           0     1     2     3     4     5
 start     0     0     0     0     0     0    start     0     0     0     0     0     0
 item0     0     0     6     6     6     6    item0     0     0     6     6    12    12

The state sentence is "dp[c] = best value with capacity c using the items processed so far, each at most once". Cell c = 4 in the buggy row says 12 with one item of value 6 — impossible. Its inputs: dp[4] (old, 0) and dp[2] + 6. But dp[2] was already updated to 6 in this same pass, so it already contained the item. That is the bug, found in one glance.

Longest palindromic subsequence of "bbbab", with the recurrence if , else . The correct order is decreasing; the buggy one loops increasing:

correct (i from n-1 down to 0)          buggy (i from 0 up to n-1)
       b   b   b   a   b                       b   b   b   a   b
   b   1   2   3   3   4                   b   1   2   2   2   2
   b   0   1   2   2   3                   b   0   1   2   2   2
   b   0   0   1   1   3                   b   0   0   1   1   2
   a   0   0   0   1   1                   a   0   0   0   1   1
   b   0   0   0   0   1                   b   0   0   0   0   1

The buggy answer is 2 instead of 4 ("bbbb"). The top row is computed first, when every row below it is still 0 — so cell reads instead of 1. Printing the table and seeing a top row that is "too flat" while lower rows are right is the signature of an order bug.

The bug catalogue

Each entry: the bug, the symptom, a minimal input that exposes it (all computed), and the fix.

1. Wrong base case

  • Bug: counting DP starts from ways[0] = 0; or climbing stairs uses w(0) = 0.
  • Symptom: all counts 0, or the sequence shifted by one.
  • Minimal input: climbing stairs : with the answer is 8; with it is 5.
  • Fix: base cases come from the state sentence applied to the smallest input. "Number of ways to make 0 with no coins" is 1: the empty selection.

2. Wrong iteration order

  • Bug: a cell is computed before a cell it reads.
  • Symptom: values too small (reads zeros) or too large (reads replaced by garbage); often correct on inputs of length 1–2.
  • Minimal input: longest palindromic subsequence of "bbbab": correct 4, increasing- order gives 2 (tables above).
  • Fix: draw the arrows of the recurrence on a 3×3 grid of cells; loop so every arrow points to an already-filled cell. Or memoize.

3. Off-by-one in indices

  • Bug: the state is defined on prefix lengths () but the loops treat it as indices (), or the reverse; s[i] used where s[i-1] was meant.
  • Symptom: the last character or item is ignored, or an index error on the last iteration; answer off by one item.
  • Minimal input: LCS of "A" and "A" — must be 1. A table of size (instead of ) with the base row missing gives 0 or crashes.
  • Fix: write the state sentence with explicit ranges ("D[i][j] = LCS of s[0..i) and t[0..j)") and keep a size- table for prefix states. Test and .

4. Integer overflow

  • Bug: counts or sums exceed 32 bits; INF + 1 wraps around.
  • Symptom (Java/C++/TypeScript bit operations): negative or absurdly small numbers. In TypeScript, plain numbers lose precision above instead of wrapping.
  • Minimal input: Fibonacci in a 32-bit int: fits, but exceeds and wraps to . In 64 bits, is the last one that fits. Integer.MAX_VALUE + 1 as an "infinity plus one coin" becomes the most negative integer and wins every min.
  • Fix: 64-bit counts; INF = MAX / 2; or the modulus the problem gives, applied after every addition and multiplication ((a * b) % MOD with a, b < MOD needs 64-bit intermediates; in TypeScript use BigInt or split the multiplication).

5. Modulo of a negative number

  • Bug: a subtraction under a modulus (inclusion–exclusion, prefix-sum differences) leaves a negative value; % in Java, C++, JavaScript and TypeScript keeps the sign of the dividend.
  • Symptom: negative answers, or wrong answers after later multiplications.
  • Minimal input: : Python's -3 % 7 is 4 (mathematically correct), but -3 % 7 is −3 in Java, C++ and TypeScript.
  • Fix: ((x % MOD) + MOD) % MOD, or add MOD before subtracting: (a - b + MOD) % MOD when .

6. Reusing items in 0/1 knapsack (iterating forward)

  • Bug: the one-row 0/1 knapsack loops capacity upward.
  • Symptom: answers too large; items counted multiple times.
  • Minimal input: one item, weight 2, value 6, capacity 5: correct 6, buggy 12 (the trace above).
  • Fix: loop capacity downward for "each item at most once"; upward is correct only for unbounded knapsack. Same for subset-sum feasibility and for 2-D budgets (LeetCode 474 Ones and Zeroes loops both budgets downward).

7. Uninitialised (unreachable states treated as reachable)

  • Bug: a max-DP over "exactly" states (exactly capacity , exactly items, ending exactly here) initialises every cell to 0.
  • Symptom: impossible configurations get value 0 and then win or feed into maxima; "impossible" is never reported.
  • Minimal input: "fill the knapsack to exactly capacity 4" with one item of weight 3, value 5. Correct: impossible (). With all cells initialised to 0, — it pretends capacity 1 was exactly filled with nothing.
  • Fix: initialise only the true base states (here ) and everything else to (or for min). Note that initialising to 0 is correct for "at most capacity" — the two problems differ only in this line, which is why the bug is so common.

8. Memo sentinel collides with a real answer

  • Bug: memo array initialised to 0 or −1, and 0 or −1 is a legitimate answer.
  • Symptom: states with that answer are recomputed every time (exponential time, but correct), or states are treated as cached before computation (wrong).
  • Fix: a sentinel outside the answer range, a separate visited array, or Optional/null.

9. State missing information

  • Bug: two histories with different futures share a state.
  • Symptom: wrong answers that the brute force contradicts; often too optimistic.
  • Minimal input: stock with cooldown on prices [1, 2, 3, 0, 2] with state (day) only cannot express "I sold yesterday, so I cannot buy today"; the correct answer is 3 (worked example 2).
  • Fix: the checklist's question 4. Add the fact the future's rules depend on.

10. Double counting

  • Bug: cases in a counting transition overlap, or orderings are counted when sets were asked for.
  • Symptom: counts too high.
  • Minimal input: ways to make 5 from coins [1, 2, 5] as multisets: 4. With amounts in the outer loop (ordered sequences) the DP gives 9.
  • Fix: split by a feature that makes cases disjoint (last coin type in a fixed order; first element; last split point).

11. Wrong answer cell

  • Bug: returning dp[n-1] for a state anchored at its end.
  • Minimal input: LIS of [3, 4, 1]: = [1, 2, 1]; L[n-1] is 1, the answer is 2.
  • Fix: if the state is "ending at ", the answer is a max (or sum) over all .

12. State not reset between test cases

  • Bug: a global memo or table reused across multiple test cases in one run (common in contests and in unit tests).
  • Symptom: the first test is right, later ones are wrong or suspiciously fast.
  • Fix: allocate per test case, or include every input-dependent value in the memo key. In Python, an lru_cache on a nested function is rebuilt per call; one on a module-level function is not.

13. Recursion depth

  • Bug: memoized recursion with chains of – states.
  • Symptom: RecursionError, StackOverflowError, RangeError, or a silent crash in C++ — but never a wrong answer.
  • Fix: tabulate. Measured limits are in DP Foundations.

Stress testing DP against brute force

Testing & Debugging Algorithms introduces the method in general; for DP it is close to mandatory, because DP is exactly the situation it was made for — a fast, subtle solution with a slow, obvious twin.

The ingredients:

  1. An oracle: a brute force so simple it is obviously right. Enumerate all subsets (), all permutations (), all paths, all split points. For DP you usually already wrote it in step 1 of the workflow — the un-memoized recursion. Even better is an oracle that does not share your recurrence (enumerate subsets rather than run the same recurrence without a cache), so a wrong recurrence cannot fool both.
  2. A generator of tiny random inputs. Small sizes (1 to 6 items), small values (1 to 10), and deliberately small ranges so collisions, ties, zeros and "does not fit" happen often. Most DP bugs need only one or two items to show.
  3. Smallest first. Generate size 1 for a while, then size 2, and so on. The first failure is then near-minimal, and you can print its table by hand. (Full "shrinking" — automatically reducing a failing input — is what property-based testing tools such as Hypothesis and QuickCheck add.)
  4. A fixed seed, so a failure reproduces, plus a loop that changes seeds when you want new coverage.
  5. A report with the input, the expected answer and the got answer.

Extra checks that cost one line each:

  • Memo versus table. If you wrote both, compare them too. Disagreement means an order bug in the table.
  • Value versus reconstruction. Recompute the value of the reconstructed solution and check it equals the reported value, and that it is legal (weights within capacity, coins summing to the amount).
  • Monotonicity and symmetry. Increasing capacity never decreases the knapsack value; LCS is symmetric in its two strings; reversing a palindrome problem's input does not change the answer.
  • Known values. Climbing stairs gives Fibonacci numbers; unique paths gives binomial coefficients.

What a passing stress test means: no bug at the sizes tested. That is much stronger than it sounds. The "small scope hypothesis" (Daniel Jackson, used in the Alloy analyzer) observes that most bugs have small counterexamples; for DP this is especially true, because a recurrence that is wrong is usually wrong already on two or three elements. It is not a proof — a bug that only appears with values above (overflow) or chains above 10,000 (stack depth) needs a separate large-input test.

Reduce to a known family

Many "new" problems are a known DP in costume. When stuck, try to match the problem against this table before inventing a state.

The problem has…It is probably…Typical stateLesson
A line of positions, each decision looks back a fixed amount1-D DPdp[i]1-D DP
Items, a capacity or target sum, use once / unlimitedKnapsackdp[i][c] or dp[c]Knapsack
One or two sequences, "subsequence", align, editSequence DPdp[i][j] over prefixesSequence DP
Pattern matching, segmentation, palindromes, interleavingString DPprefix × prefixString DP
A grid with one-way movesGrid DPdp[r][c]Grid & Path DP
"merge / burst / split a range", answer depends on the last operation inside a rangeInterval DPdp[l][r]Interval DP
Cut an array into contiguous groupsPartition DPdp[k][i]Partition DP
A tree, choose nodes subject to parent/child rulesTree DPdp[v][flag]Tree DP
A directed acyclic graph, longest path, count pathsDAG DPdp[v] in topological orderDAG DP
, "visit all", "assign each once"Bitmask DPdp[mask] or dp[mask][last]Bitmask DP
Sums over all submasks / supersetsSOS DPf[mask]SOS DP
"How many integers in have a digit property"Digit DP(pos, tight, property)Digit DP
Tiling a narrow grid with dominoes / shapesBroken-profile DP(cell, profile mask)Broken-Profile DP
"Count the arrangements modulo "Counting DPcounts with %Counting DP
"Expected value", "probability that"Probability DPE[state]Probability DP
Two players alternate, both play optimallyGame DPwin[state] or score differenceGame DP
Linear recurrence, up to Matrix exponentiationtransition matrixMatrix Exponentiation
Correct DP, too slow, transition is a min over a rangeDP optimisationsame state, faster transitionDP Optimizations
Moves in all directions, non-negative costsNot DP: shortest pathdist[v]Shortest Paths

Worked examples: from stuck to state found

Each example follows the same shape: the problem in my own words, the first attempt and why it fails, the question that unlocks it, the final state with transition, and verified numbers.

Example 1: House robber — "position" is not enough, until you redefine it

Houses in a row hold amounts of money; robbing two adjacent houses triggers an alarm. Maximise the total.

Stuck: "dp[i] = best total if I rob house ." Then — a max over all earlier houses, , and the answer is a max over all . Workable, but it smells wrong.

The question: what does the decision at house need to know? Only whether house was robbed. Two fixes:

  • Add the bit: dp[i][robbed_i].
  • Or make the state "best total from the first houses, whatever happened to house " and push the bit into the transition: either house is skipped (value ) or robbed, in which case house is skipped ().

State found: = most money from houses . , , . , two variables.

Numbers: [2, 7, 9, 3, 1] → running bests 2, 7, 11, 11, 12 (2 + 9 + 1). The brute force makes 35,421 calls on 20 houses; the DP makes 20 steps.

Example 2: Stock trading with a cooldown — the future's rules define the state

Given daily prices, buy and sell one share at a time, as often as you like, but after selling you must wait one day before buying again. Maximise profit.

Stuck: "dp[i] = best profit by day ." The transition needs to know whether you hold a share (can you sell today?) and whether you sold yesterday (can you buy today?). The state does not say.

The question (checklist 4): what do tomorrow's rules depend on? Holding or not; and if not holding, whether today was a sale day. That is three situations.

State found: for each day, three values:

  • hold = best profit so far while holding a share,
  • sold = best profit so far having sold today (so tomorrow is a cooldown),
  • free = best profit so far, not holding, free to buy tomorrow.

Transitions for price : hold' = max(hold, free - p), sold' = hold + p, free' = max(free, sold). Start: hold = -∞, sold = -∞, free = 0. Answer: max(sold, free) after the last day.

Numbers: prices [1, 2, 3, 0, 2]:

DayPriceholdsoldfree
01−1−∞0
12−110
23−121
301−12
42132

Answer 3: buy at 1, sell at 2, cooldown, buy at 0, sell at 2. This "small state machine per position" pattern solves the whole family of stock problems (with transactions, with fees).

Example 3: Paint house — "what was the last choice?"

Each of houses must be painted one of 3 colours, with a cost per house per colour; adjacent houses must differ. Minimise the total cost.

Stuck: "dp[i] = cheapest way to paint the first houses." Whether house may be red depends on house 's colour, which the state forgot.

State found: = cheapest way to paint houses with house painted colour . . Answer . , and with colours using the "best and second best of the previous row" trick.

Numbers: costs [[17, 2, 17], [16, 16, 5], [14, 3, 19]]: rows [17, 2, 17] → [18, 33, 7] → [21, 10, 37]; answer 10 (colour 1, then 2, then 1: 2 + 5 + 3).

Example 4: Decode ways — look back exactly as far as the rules do

A digit string encodes letters with A = 1 … Z = 26. Count the ways to decode it.

Stuck: trying to track "which letters so far" — a list, not a state.

The question: the last letter of a decoding used either the last one digit or the last two digits. Nothing else about the past matters.

State found: = number of decodings of the prefix of length . , . .

Numbers: "226" → = [1, 1, 2, 3], answer 3 (BZ, VF, BBF). "11106" → [1, 1, 2, 3, 2, 2], answer 2 (the "0" forces "10", which cuts the possibilities). "06" → 0 (a leading zero has no letter). The zero cases are where the bug catalogue's base-case and off-by-one entries strike; stress-test against a brute force that tries every split.

Example 5: Burst balloons — think about the last move, not the first

Balloons with numbers in a row; bursting balloon earns (left neighbour) × × (right neighbour), where neighbours are the nearest unburst balloons (missing neighbours count as 1). Burst them all; maximise the total.

Stuck: "which balloon do I burst first?" After bursting first, its neighbours become adjacent, so the left and right parts are no longer independent — the subproblems interact. The state would have to remember which balloons are gone: a bitmask, .

The question (checklist 6): choose a different decision to split on. Which balloon is burst last in the range? If is the last balloon burst between fixed walls and (exclusive), then while everything else in and bursts, is still standing and separates them. The two sides are independent, and 's own reward is , known in advance.

State found: pad the array with 1 at both ends. = best total from bursting every balloon strictly between and . , . Order: by increasing . .

Numbers: [3, 1, 5, 8] → 167 (burst 1, 5, 3, 8: ).

This "last operation" move is the key idea of Interval DP.

Example 6: Counting numbers by digit sum — the state is a position in a number

How many integers from 0 to 2024 have digit sum exactly 10?

Stuck: looping over all numbers works for 2024 but not for . What is the "subproblem"?

The question: build the number digit by digit from the left. What does the future need? (1) Which position we are at. (2) The digit sum so far — the objective depends on it. (3) Whether the digits so far are equal to the prefix of the upper bound ("tight"): if they are, the next digit may not exceed the bound's digit; if we already went below, any digit 0–9 is allowed. Which digits we chose does not matter beyond those three facts.

State found: . Transition: try every allowed digit , move to . Base: at the end, count 1 if . Prune when .

Numbers: the answer is 120 (confirmed by brute force over 0..2024). The memo held 58 states, out of a possible ; for an upper bound of and any target sum the state space is at most (19 digit positions, digit sums 0 to 162, tight or not) — a few thousand states instead of numbers. Deep dive: Digit DP.

Example 7: Assigning workers to jobs — when the past is a set

workers, jobs, cost[i][j] for worker doing job . Each worker does exactly one job, each job is done once. Minimise the total. (.)

Stuck: "dp[i] = cheapest way to assign the first workers." Which jobs are still free depends on exactly which jobs the first workers took — not just how many.

The question: the future needs the set of jobs already taken. With , a set fits in a 20-bit integer (a bitmask).

Dimension audit: the obvious state (worker index, used-jobs mask) has a derivable dimension: if we assign workers in order, the worker index equals the number of 1-bits in the mask. Drop it.

State found: = cheapest cost to give the jobs in to workers . Transition: worker takes some job : . . Order: increasing mask. — for about , versus permutations.

Numbers: cost [[9, 2, 7], [6, 4, 3], [5, 8, 1]] → 9 (worker 0 → job 1, worker 1 → job 0, worker 2 → job 2: 2 + 6 + 1). Brute force over all 6 permutations agrees. Deep dive: Bitmask DP; the polynomial-time alternative is the Hungarian algorithm in Bipartite Matching.

Example 8: Longest increasing subsequence — anchor the state at its end

Length of the longest strictly increasing subsequence.

Stuck: "dp[i] = LIS within the first elements." To decide whether extends it, you need the last value of that subsequence; there might be several LISs of the same length with different last values, and the state kept none of them.

The question: the future needs the last value. Rather than adding it as a dimension, define the state so the last value is known: the subsequence ends at .

State found: = LIS ending at index ; ; answer (bug 11 if you forget).

Numbers: [10, 9, 2, 5, 3, 7, 101, 18] → = [1, 1, 1, 2, 2, 3, 4, 4], answer 4. [3, 4, 1] → = [1, 2, 1], answer 2, not .

The pattern across all eight

#ProblemWhat the future neededStateMove that found it
1House robberWhether the previous house was robbed, bit absorbed in transitionChecklist 4
2Stock with cooldownHolding? Just sold?(day, hold/sold/free)Future's rules
3Paint housePrevious colour(house, colour)"Last choice"
4Decode waysOnly the last 1–2 digitsprefix lengthLook back as far as the rules
5Burst balloonsIndependence of the two sidesinterval Last operation, not first
6Digit sum countPosition, sum so far, tight flagBuild digit by digit
7AssignmentSet of used jobsBitmask; drop derivable index
8LISLast value takenending at Anchor at the end

The ladder: brute force → better → optimal

The debugging ladder for any DP — each rung is checked against the one below it.

RungWhat you writeCostWhy it is better than the rung belowWhat it is for
1Exhaustive enumeration (subsets, permutations)exponential—Oracle; shares no logic with the DP
2Brute-force recursion with state parametersexponentialSame answers, now with an explicit stateReveals the state; second oracle
3Memoized recursionstates × transitionsPolynomial; correct by construction if rung 2 isFirst fast version
4TabulationsameNo recursion limit, lower overheadProduction; enables rolling
5Rolled / optimised tablesame time, less spaceMemoryFinal version, if needed

For 0/1 knapsack: rung 1 is , rungs 3–4 are time and space, rung 5 is space. Most bugs enter between rungs 4 and 5 (order, direction), which is precisely where a stress test against rung 1 pays off.

Correctness: what the tools prove

  • Brute force → memoization preserves correctness exactly, if the recursion is a pure function of its parameters. Memoization only skips recomputation of identical calls.
  • Memoization → tabulation preserves correctness if the loop order is a topological order of the dependency graph — every state after the states it reads. The induction is the one in DP Foundations.
  • Rolling arrays preserve correctness if no cell is overwritten before every cell that reads its old value has been computed. For one-row 0/1 knapsack, dp[c] reads the old dp[c - w]; looping downward means dp[c - w] (smaller index) is overwritten after dp[c], so it is still old. Looping upward breaks exactly this.
  • Stress testing proves nothing in general, but for DP it has excellent coverage: the state space for inputs of size with values already exercises every branch of most transitions, every base case and every boundary. What it does not cover — large values (overflow), long chains (stack depth), time limits — needs one large deterministic test each.
  • The state sentence is the induction hypothesis. If you cannot say it, you cannot prove the DP, and you cannot debug it either: debugging is checking cells against the hypothesis.

Complexity

  • The harness: trials × (oracle cost + DP cost). With subsets, the oracle is ; at that is a few hundred operations, so 300 trials run in milliseconds in every language. Push to 15–20 for a deeper check; beyond that, use a second, independent polynomial solution (memo versus table) as the oracle.
  • The state budget: states × transitions per state. Rough limits for one second: about simple operations in C++ and Java, a few times less in TypeScript, about in Python.
  • Printing a table is — only ever do it on tiny inputs.

Implementation

A complete stress-test harness in each language. It contains: a deterministic random generator (the "MINSTD" Lehmer generator, , chosen because it gives identical numbers in all four languages without 64-bit tricks in TypeScript), a brute-force oracle over all subsets, a correct one-row 0/1 knapsack, a buggy one that loops capacity upward, a generator that grows the input size from 1 to 6, and a stress function that returns the first mismatch. Every version prints:

knapsack_dp: 300 random tests passed
knapsack_dp_buggy: FAIL weights=[2] values=[6] cap=5 expected=6 got=12

To use it on your own DP, replace brute, the DP functions and random_case; keep the loop.

from typing import Callable, List, Optional, Tuple

Case = Tuple[List[int], List[int], int]          # (weights, values, capacity)


class Rng:
    """Lehmer / MINSTD generator: same numbers in every language, so a failing
    seed found in Python reproduces in Java, C++ and TypeScript."""

    def __init__(self, seed: int) -> None:
        self.state = seed

    def next(self) -> int:
        self.state = self.state * 48271 % 2147483647
        return self.state

    def randint(self, lo: int, hi: int) -> int:   # inclusive on both ends
        return lo + self.next() % (hi - lo + 1)


def brute(case: Case) -> int:
    """Oracle: try all 2^n subsets. Obviously correct, hopelessly slow."""
    w, v, cap = case
    n, best = len(w), 0
    for mask in range(1 << n):
        tw = sum(w[i] for i in range(n) if mask >> i & 1)
        tv = sum(v[i] for i in range(n) if mask >> i & 1)
        if tw <= cap:
            best = max(best, tv)
    return best


def knapsack_dp(case: Case) -> int:
    """0/1 knapsack with one row: capacity loop runs DOWNWARD."""
    w, v, cap = case
    dp = [0] * (cap + 1)
    for i in range(len(w)):
        for c in range(cap, w[i] - 1, -1):
            dp[c] = max(dp[c], dp[c - w[i]] + v[i])
    return dp[cap]


def knapsack_dp_buggy(case: Case) -> int:
    """The classic bug: capacity loop runs UPWARD, so an item can be reused."""
    w, v, cap = case
    dp = [0] * (cap + 1)
    for i in range(len(w)):
        for c in range(w[i], cap + 1):
            dp[c] = max(dp[c], dp[c - w[i]] + v[i])
    return dp[cap]


def random_case(rng: Rng, n: int) -> Case:
    w = [rng.randint(1, 5) for _ in range(n)]
    v = [rng.randint(1, 9) for _ in range(n)]
    return w, v, rng.randint(0, 10)


def stress(solve: Callable[[Case], int], trials: int = 300,
           seed: int = 2026) -> Optional[Tuple[Case, int, int]]:
    """Compare solve() with brute() on random cases, smallest sizes first.
    Returns (case, expected, got) for the first mismatch, or None."""
    rng = Rng(seed)
    for t in range(trials):
        n = 1 + t * 6 // trials                    # n = 1 for the first 50 trials, ..., 6 at the end
        case = random_case(rng, n)
        expected, got = brute(case), solve(case)
        if expected != got:
            return case, expected, got
    return None


if __name__ == "__main__":
    assert stress(knapsack_dp) is None
    print("knapsack_dp: 300 random tests passed")
    failure = stress(knapsack_dp_buggy)
    assert failure is not None
    (w, v, cap), expected, got = failure
    print(f"knapsack_dp_buggy: FAIL weights={w} values={v} cap={cap} "
          f"expected={expected} got={got}")
import java.util.Arrays;
import java.util.function.ToIntFunction;

public class Stress {
    record Case(int[] w, int[] v, int cap) {}
    record Failure(Case c, int expected, int got) {}

    // Lehmer / MINSTD: identical sequence in all four languages.
    static final class Rng {
        long state;
        Rng(long seed) { state = seed; }
        long next() { state = state * 48271 % 2147483647L; return state; }
        int randint(int lo, int hi) { return (int) (lo + next() % (hi - lo + 1)); }
    }

    // Oracle: all 2^n subsets.
    static int brute(Case k) {
        int n = k.w().length, best = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            int tw = 0, tv = 0;
            for (int i = 0; i < n; i++) {
                if ((mask >> i & 1) == 1) { tw += k.w()[i]; tv += k.v()[i]; }
            }
            if (tw <= k.cap()) best = Math.max(best, tv);
        }
        return best;
    }

    // 0/1 knapsack, one row, capacity loop runs DOWNWARD.
    static int knapsackDp(Case k) {
        int[] dp = new int[k.cap() + 1];
        for (int i = 0; i < k.w().length; i++) {
            for (int c = k.cap(); c >= k.w()[i]; c--) {
                dp[c] = Math.max(dp[c], dp[c - k.w()[i]] + k.v()[i]);
            }
        }
        return dp[k.cap()];
    }

    // The classic bug: capacity loop runs UPWARD, so an item can be reused.
    static int knapsackDpBuggy(Case k) {
        int[] dp = new int[k.cap() + 1];
        for (int i = 0; i < k.w().length; i++) {
            for (int c = k.w()[i]; c <= k.cap(); c++) {
                dp[c] = Math.max(dp[c], dp[c - k.w()[i]] + k.v()[i]);
            }
        }
        return dp[k.cap()];
    }

    static Case randomCase(Rng rng, int n) {
        int[] w = new int[n], v = new int[n];
        for (int i = 0; i < n; i++) w[i] = rng.randint(1, 5);
        for (int i = 0; i < n; i++) v[i] = rng.randint(1, 9);
        return new Case(w, v, rng.randint(0, 10));
    }

    // First mismatch against brute(), smallest sizes first; null if none.
    static Failure stress(ToIntFunction<Case> solve, int trials, long seed) {
        Rng rng = new Rng(seed);
        for (int t = 0; t < trials; t++) {
            int n = 1 + t * 6 / trials;
            Case k = randomCase(rng, n);
            int expected = brute(k), got = solve.applyAsInt(k);
            if (expected != got) return new Failure(k, expected, got);
        }
        return null;
    }

    public static void main(String[] args) {
        if (stress(Stress::knapsackDp, 300, 2026) != null) throw new AssertionError("dp failed");
        System.out.println("knapsack_dp: 300 random tests passed");
        Failure f = stress(Stress::knapsackDpBuggy, 300, 2026);
        if (f == null) throw new AssertionError("bug not found");
        System.out.println("knapsack_dp_buggy: FAIL weights=" + Arrays.toString(f.c().w())
                + " values=" + Arrays.toString(f.c().v()) + " cap=" + f.c().cap()
                + " expected=" + f.expected() + " got=" + f.got());
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <optional>
#include <vector>
using namespace std;

struct Case { vector<int> w, v; int cap; };
struct Failure { Case c; int expected, got; };

// Lehmer / MINSTD: identical sequence in all four languages.
struct Rng {
    int64_t state;
    explicit Rng(int64_t seed) : state(seed) {}
    int64_t next() { state = state * 48271 % 2147483647LL; return state; }
    int randint(int lo, int hi) { return int(lo + next() % (hi - lo + 1)); }
};

// Oracle: all 2^n subsets.
int brute(const Case& k) {
    int n = k.w.size(), best = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        int tw = 0, tv = 0;
        for (int i = 0; i < n; ++i)
            if (mask >> i & 1) { tw += k.w[i]; tv += k.v[i]; }
        if (tw <= k.cap) best = max(best, tv);
    }
    return best;
}

// 0/1 knapsack, one row, capacity loop runs DOWNWARD.
int knapsackDp(const Case& k) {
    vector<int> dp(k.cap + 1, 0);
    for (size_t i = 0; i < k.w.size(); ++i)
        for (int c = k.cap; c >= k.w[i]; --c)
            dp[c] = max(dp[c], dp[c - k.w[i]] + k.v[i]);
    return dp[k.cap];
}

// The classic bug: capacity loop runs UPWARD, so an item can be reused.
int knapsackDpBuggy(const Case& k) {
    vector<int> dp(k.cap + 1, 0);
    for (size_t i = 0; i < k.w.size(); ++i)
        for (int c = k.w[i]; c <= k.cap; ++c)
            dp[c] = max(dp[c], dp[c - k.w[i]] + k.v[i]);
    return dp[k.cap];
}

Case randomCase(Rng& rng, int n) {
    Case k;
    for (int i = 0; i < n; ++i) k.w.push_back(rng.randint(1, 5));
    for (int i = 0; i < n; ++i) k.v.push_back(rng.randint(1, 9));
    k.cap = rng.randint(0, 10);
    return k;
}

// First mismatch against brute(), smallest sizes first.
optional<Failure> stress(const function<int(const Case&)>& solve, int trials, int64_t seed) {
    Rng rng(seed);
    for (int t = 0; t < trials; ++t) {
        int n = 1 + t * 6 / trials;
        Case k = randomCase(rng, n);
        int expected = brute(k), got = solve(k);
        if (expected != got) return Failure{k, expected, got};
    }
    return nullopt;
}

string show(const vector<int>& a) {
    string s = "[";
    for (size_t i = 0; i < a.size(); ++i) s += (i ? ", " : "") + to_string(a[i]);
    return s + "]";
}

int main() {
    assert(!stress(knapsackDp, 300, 2026).has_value());
    cout << "knapsack_dp: 300 random tests passed\n";
    auto f = stress(knapsackDpBuggy, 300, 2026);
    assert(f.has_value());
    cout << "knapsack_dp_buggy: FAIL weights=" << show(f->c.w) << " values=" << show(f->c.v)
         << " cap=" << f->c.cap << " expected=" << f->expected << " got=" << f->got << "\n";
}
type Case = { w: number[]; v: number[]; cap: number };
type Failure = { c: Case; expected: number; got: number };

// Lehmer / MINSTD: identical sequence in all four languages.
// state * 48271 < 2^53, so plain numbers stay exact.
class Rng {
  state: number;
  constructor(seed: number) {
    this.state = seed;
  }
  next(): number {
    this.state = (this.state * 48271) % 2147483647;
    return this.state;
  }
  randint(lo: number, hi: number): number {
    return lo + (this.next() % (hi - lo + 1));
  }
}

// Oracle: all 2^n subsets.
function brute(k: Case): number {
  const n = k.w.length;
  let best = 0;
  for (let mask = 0; mask < 1 << n; mask++) {
    let tw = 0, tv = 0;
    for (let i = 0; i < n; i++) {
      if ((mask >> i) & 1) { tw += k.w[i]; tv += k.v[i]; }
    }
    if (tw <= k.cap) best = Math.max(best, tv);
  }
  return best;
}

// 0/1 knapsack, one row, capacity loop runs DOWNWARD.
function knapsackDp(k: Case): number {
  const dp = new Array<number>(k.cap + 1).fill(0);
  for (let i = 0; i < k.w.length; i++) {
    for (let c = k.cap; c >= k.w[i]; c--) {
      dp[c] = Math.max(dp[c], dp[c - k.w[i]] + k.v[i]);
    }
  }
  return dp[k.cap];
}

// The classic bug: capacity loop runs UPWARD, so an item can be reused.
function knapsackDpBuggy(k: Case): number {
  const dp = new Array<number>(k.cap + 1).fill(0);
  for (let i = 0; i < k.w.length; i++) {
    for (let c = k.w[i]; c <= k.cap; c++) {
      dp[c] = Math.max(dp[c], dp[c - k.w[i]] + k.v[i]);
    }
  }
  return dp[k.cap];
}

function randomCase(rng: Rng, n: number): Case {
  const w: number[] = [], v: number[] = [];
  for (let i = 0; i < n; i++) w.push(rng.randint(1, 5));
  for (let i = 0; i < n; i++) v.push(rng.randint(1, 9));
  return { w, v, cap: rng.randint(0, 10) };
}

// First mismatch against brute(), smallest sizes first; null if none.
function stress(solve: (k: Case) => number, trials = 300, seed = 2026): Failure | null {
  const rng = new Rng(seed);
  for (let t = 0; t < trials; t++) {
    const n = 1 + Math.floor((t * 6) / trials);
    const c = randomCase(rng, n);
    const expected = brute(c), got = solve(c);
    if (expected !== got) return { c, expected, got };
  }
  return null;
}

if (stress(knapsackDp) !== null) throw new Error("dp failed");
console.log("knapsack_dp: 300 random tests passed");
const f = stress(knapsackDpBuggy);
if (f === null) throw new Error("bug not found");
console.log(
  `knapsack_dp_buggy: FAIL weights=[${f.c.w.join(", ")}] values=[${f.c.v.join(", ")}] ` +
    `cap=${f.c.cap} expected=${f.expected} got=${f.got}`,
);

Running it from a script in competitive programming usually means three files (solution, brute, gen) and a shell loop that diffs their outputs; the in-process version above is easier to start with and is what you want inside a unit test suite.

Real-world uses

  • Competitive programming. Stress testing against a brute force with a random generator is standard practice among competitive programmers for finding wrong-answer bugs; the cp-algorithms and Codeforces communities document the three-file setup (solution, brute force, generator plus a loop).
  • Differential testing in industry. William McKeeman's "Differential Testing for Software" (Digital Technical Journal, 1998) described comparing compilers against each other on generated programs; Csmith (Yang, Chen, Eide, Regehr, PLDI 2011) used the same idea to find hundreds of bugs in GCC and LLVM. A brute-force oracle is a differential test with a deliberately simple second implementation.
  • Property-based testing. QuickCheck (Claessen and Hughes, ICFP 2000) and Python's Hypothesis generate random inputs, check properties, and shrink failures to minimal examples — the automated version of "smallest first".
  • Bioinformatics and diff tools. Alignment and diff implementations (which are DPs) are routinely validated against reference implementations on generated sequences, because their optimised forms (banded DP, Myers' diff, SIMD alignment) are easy to get subtly wrong.

Pitfalls & edge cases

  • An oracle that shares the bug. If the brute force is your DP's recurrence without the memo, a wrong recurrence fools both. Prefer enumeration (all subsets, all permutations) as the oracle.
  • Inputs too large to brute force. Keep tiny; that is the point. If the DP has a value dimension (capacity), keep values small too.
  • Ranges too wide. Random values from 1 to almost never produce ties, zeros or exact fits — the cases that break DPs. Use tiny ranges.
  • Non-unique answers. When the problem asks for a solution (a path, a set), compare values, and validate the reconstructed solution separately (legal? achieves the value?).
  • Floating point. Probability and expected-value DPs: compare with a tolerance, e.g. .
  • Forgetting the edge inputs. Random generation rarely produces . Add explicit tests for empty input, capacity 0, a single element, all equal elements.
  • Modulus too big to notice overflow. With answers under , a missing % MOD only shows on large inputs; include one large deterministic case in the tests.

Variations

  • Shrinking. On failure, try removing each element or decreasing each value and keep the change if the test still fails; repeat. You get a locally minimal counterexample automatically.
  • Exhaustive small-scope testing. Instead of random inputs, enumerate all inputs up to a size (all arrays of length over values 0..3 is only 341 arrays). It removes luck from the process.
  • Two fast solutions as each other's oracle. For sizes the brute force cannot reach, compare memo against table, or LIS against LIS.
  • Assertion-heavy DP. Assert invariants inside the loops: counts non-negative, values within known bounds, monotonicity in capacity. Turn them off for speed later.
  • Debugging state machines visually. For DPs whose state is a small automaton (stock problems, regex matching), draw the automaton; transitions missing from the picture are missing from the code.

Practice ladder

Each problem is described in my own words; follow the link for the full statement. For every one, write the brute force first and stress-test your DP against it.

1. House Robber (LeetCode 198) — Worked example 1.

Hint

Brute force: rob(i) = max(rob(i+1), a[i] + rob(i+2)). Memoize, then roll into two variables.

2. Decode Ways (LeetCode 91) — Worked example 4. The zeros are the whole difficulty.

Solution
def num_decodings(s):
    prev2, prev1 = 1, 1 if s and s[0] != "0" else 0      # D[0], D[1]
    if not s:
        return 0
    for i in range(2, len(s) + 1):
        cur = prev1 if s[i - 1] != "0" else 0
        if 10 <= int(s[i - 2:i]) <= 26:
            cur += prev2
        prev2, prev1 = prev1, cur
    return prev1


assert num_decodings("226") == 3
assert num_decodings("11106") == 2
assert num_decodings("06") == 0

Stress-test idea: a brute force that tries every split into 1- and 2-digit pieces and checks each piece is in 1..26 without a leading zero.

3. Best Time to Buy and Sell Stock with Cooldown (LeetCode 309) — Worked example 2.

Solution
def max_profit(prices):
    NEG = float("-inf")
    hold, sold, free = NEG, NEG, 0
    for p in prices:
        hold, sold, free = max(hold, free - p), hold + p, max(free, sold)
    return max(sold, free)


assert max_profit([1, 2, 3, 0, 2]) == 3
assert max_profit([1]) == 0

All three updates use the previous day's values — Python's tuple assignment does that for you; in other languages use temporaries.

4. Combination Sum IV (LeetCode 377) — Count ordered sequences of numbers summing to a target.

Hint

This is bug 10 on purpose: amounts outer, numbers inner. Compare with Coin Change II (LeetCode 518), which wants the other loop order.

5. Ones and Zeroes (LeetCode 474) — 0/1 knapsack with two budgets (zeros and ones).

Hint

dp[z][o] with both loops downward. Write the upward version too and watch a stress test catch it.

6. Longest Palindromic Subsequence (LeetCode 516) — Bug 2's example.

Hint

from down to 0, from up. Print the table for "bbbab".

7. Number of Dice Rolls With Target Sum (LeetCode 1155) — Count ways dice with faces sum to a target, modulo .

Hint

State (dice used, sum). A prefix-sum speed-up needs a subtraction under the modulus — bug 5.

8. Burst Balloons (LeetCode 312) — Worked example 5.

Solution
def max_coins(nums):
    a = [1] + nums + [1]
    n = len(a)
    best = [[0] * n for _ in range(n)]      # best[l][r]: burst everything strictly between l and r
    for length in range(2, n):               # r - l
        for l in range(0, n - length):
            r = l + length
            best[l][r] = max(best[l][k] + a[l] * a[k] * a[r] + best[k][r] for k in range(l + 1, r))
    return best[0][n - 1]


assert max_coins([3, 1, 5, 8]) == 167
assert max_coins([1, 5]) == 10

. Brute force for the stress test: try all bursting orders.

9. Minimum XOR Sum of Two Arrays (LeetCode 1879) — Pair up two arrays of length to minimise the sum of XORs.

Hint

Worked example 7 with cost : dp[mask], worker index = popcount.

10. Matching (AtCoder Educational DP Contest O) — Count perfect matchings in a bipartite compatibility matrix, , modulo .

Hint

Counting version of example 7. ; Python needs care at .

11. Counting Numbers (CSES 2220) — Count integers in with no two adjacent equal digits.

Hint

Digit DP: (position, previous digit, tight, started). The "started" flag handles leading zeros, which do not count as a previous digit.

12. Non-negative Integers without Consecutive Ones (LeetCode 600) — Count integers whose binary form has no "11".

Hint

Digit DP over bits: (bit position, previous bit, tight). Brute-force every integer up to a few thousand to check.

Common mistakes & interview follow-ups

"Walk me through how you found the state." Interviewers value the reasoning more than the recurrence. Say it in checklist order: decisions, what changes, what the future needs, then the sentence. "The future needs to know whether I hold a stock and whether I sold yesterday, so I have three states per day."

"How do you know your DP is correct?" The state sentence as an induction hypothesis, plus "I would stress-test it against an exhaustive search on small inputs". Offering the test unprompted is a strong signal.

"Your solution fails on this input — debug it." Print (or say aloud) the table for the input, check cells from the base upward against the state sentence, and name the first wrong cell. Do not start editing code before you have found that cell.

"Can you reduce the dimensions?" Run the audit aloud: derivable (cherry pickup's columns, bitmask's worker index), unnecessary, or value-in-state.

"Why does 0/1 knapsack loop backward?" Because the cell you read must still hold the previous item's value; give the one-item counterexample (weight 2, value 6, capacity 5 → 12).

Mistakes interviewers watch for: writing code before the state sentence; changing the state definition halfway through; a greedy "proof" by one example; never testing or ; returning dp[n-1] for an "ending at" state.

Quick quiz

1. State the one property a DP state must have.

Answer

Any two histories that reach the same state must have the same possible futures with the same value (the past is fully summarised).

2. In the stress-test trace, why do trials 3, 4, 6 and 7 pass for the buggy DP?

Answer

In each, the item cannot be taken twice within the capacity (it does not fit even once, or fits once but not twice), so reusing it is impossible and both loop directions agree.

3. Your exact-capacity knapsack returns 5 when the right answer is "impossible". What is the likely bug?

Answer

Unreachable states initialised to 0 instead of (bug 7). Only should be 0.

4. In Java, (a - b) % MOD printed −3. Fix it.

Answer

((a - b) % MOD + MOD) % MOD, or (a - b + MOD) % MOD when both are already reduced.

5. Why is the bitmask assignment DP indexed only by the mask?

Answer

Assigning workers in order, the next worker's index equals the number of jobs already taken, popcount(mask). It is derivable, so it is not a dimension.

6. Why split burst balloons on the last balloon burst rather than the first?

Answer

While the last balloon in a range is still standing it separates the left and right parts, which are then independent; after the first burst the two sides become neighbours and interact.

Further reading / sources

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed., §14.3 "Elements of dynamic programming" — optimal substructure, subproblem graphs, and how a wrong subproblem choice fails.
  • Jeff Erickson, Algorithms (2019), Chapter 3 — deriving DP from a backtracking recursion, the approach of this lesson's workflow (free online).
  • Steven Skiena, The Algorithm Design Manual, 3rd ed. (2020), Chapter 10 — "War story" sections on finding the right DP formulation.
  • William M. McKeeman, "Differential Testing for Software", Digital Technical Journal 10(1), 1998.
  • Xuejun Yang, Yang Chen, Eric Eide, John Regehr, "Finding and Understanding Bugs in C Compilers", PLDI 2011 (Csmith).
  • Koen Claessen and John Hughes, "QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs", ICFP 2000; Hypothesis documentation.
  • Daniel Jackson, Software Abstractions (MIT Press, 2006) — the small scope hypothesis.
  • Stephen K. Park and Keith W. Miller, "Random Number Generators: Good Ones Are Hard to Find", Communications of the ACM 31(10), 1988 — the minimal standard generator; the multiplier 48271 is from their 1993 follow-up remarks.
  • cp-algorithms, Introduction to Dynamic Programming.
  • AtCoder Educational DP Contest, problem list — 26 problems covering most families; ideal for practising the checklist.

Lessons: previous — DP Optimizations · next — Module 6 Capstone · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: DP Foundations · Testing & Debugging Algorithms · Backtracking & Recursion · Grid & Path DP · String DP · Bit Manipulation · Bipartite Matching.