Dynamic Programming

By the end of this lesson you will be able to recognize when a problem has optimal substructure and overlapping subproblems, solve it both top-down (memoization) and bottom-up (tabulation), read and animate a DP table cell by cell (seeing exactly which earlier cells each new cell depends on), and reconstruct an actual optimal solution — not just its value — for rod cutting, matrix-chain multiplication, longest common subsequence, and optimal binary search trees. Dynamic programming is among the most interview-relevant ideas in this whole course, so the question bank at the end is extra deep.

0. What is Dynamic Programming?

A reliable way to design a DP is a four-step recipe, and every example on this page follows it in order:

1. Characterize the structure of an optimal solution — what does it look like, and what smaller pieces is it made of?
2. Recursively define the value of an optimal solution in terms of optimal solutions to smaller subproblems.
3. Compute the value, typically bottom-up (smallest subproblems first).
4. Construct an optimal solution from the computed information (skip this step if you only need the value, not the actual solution).

Overlapping subproblems, counted in code: naive Fibonacci makes an exponential number of calls for the same few values; remembering answers makes it linear.

Rod cutting

Indexing note. Piece lengths start at 1, but Dart lists start at 0, so the price of a piece of length i is stored in price[i − 1]. The pseudocode below uses exactly that, so it reads the same as the Dart.

There are 2n-1 different ways to cut a rod of length n (independently decide, at each of the n-1 possible cut points, whether to cut there or not) — so trying every way directly is exponential. Let rn be the maximum revenue obtainable for a rod of length n. Thinking of the first piece (of some length i, from 1 to n) and then optimally cutting up what's left (length n-i) gives the recurrence below, with the convention r0 = 0:

rn = max1≤i≤n ( pricei + rn-i )

Both claims in code: every way of cutting is one bitmask of the n−1 cut points (so there are 2ⁿ⁻¹ of them), and the recurrence gives the same best revenue as trying them all.

cutRodNaive — the naive recursive algorithm

Input size → what’s feasible: n ≤ ~25 → 2²⁵ ≈ 3.4·10⁷ calls, fine (well under a second); n = 30 → 2³⁰ ≈ 10⁹ calls ≈ 10 s; n = 50 → ≈ 10¹⁵ calls, never finishes. Use the DP versions below for anything larger.

The most direct translation of that recurrence into code just recomputes rn-i from scratch, recursively, every single time it's needed:

The call count T(n) = 2ⁿ, as code: first from the recurrence, then by instrumenting the real cutRodNaive.

memoCutRod — top-down with a memo table

Input size → what’s feasible: n ≤ 10⁴ → n(n+1)/2 ≈ 5·10⁷ loop steps ≈ 0.5 s, recursion depth n (fine up to about 10⁴ in Dart); n = 10⁵ → 5·10⁹ steps, too slow for ~1 s.

The fix: before recursing on a subproblem, check whether it's already been solved and stored in a table memo[0..n] (initialized to a sentinel meaning "unknown" — −1 works, because real answers are never negative). If it's already there, return the stored value instantly instead of recursing.

The code splits into two procedures. memoCutRod (4 lines) only prepares the empty scratchpad memo and calls the helper; memoAux (10 lines) does the real recursion. First the wrapper:

Now the helper. Each row of the log is one call of memoAux; watch the array memo fill up and count how many calls end as instant "memo hits":

bottomUpCutRod — solve subproblems smallest-first

Input size → what’s feasible: n ≤ 10⁴ → ≈ 5·10⁷ steps ≈ 0.5 s with an 80 KB table (10⁴+1 ints) and no recursion-depth limit; n = 10⁵ → 5·10⁹ steps, too slow.

The other DP strategy: skip recursion entirely, and just fill the table r[0..n] in order of increasing length, so that whenever you need r[len − first] it's already sitting in the table (because len − first < len, and you filled smaller entries first).

The Θ(n²) bound, counted: Σ len = n(n+1)/2 loop steps for the table, and the same loop work for the memoized version (plus instant memo hits).

The subproblem graph

Input size → what’s feasible: n = 10⁴ → 10⁴+1 vertices and ≈ 5·10⁷ edges. You never build this graph in memory — the loops simply walk it in the right order.

Draw one node per subproblem (lengths 0..n) and an edge from len to every len-first it directly needs (i.e. every shorter length). For rod cutting that means node len has edges to all of 0, 1, …, len-1 — a dense "each node depends on everything smaller" graph. bottomUpCutRod's visiting order is exactly a reverse topological sort of this graph (dependencies before dependents), and memoCutRod's recursion is a depth-first search of it, just visiting the same nodes in a different order and skipping any node already marked "done". A handy rule of thumb: a DP's running time is usually proportional to the number of vertices plus edges of its subproblem graph — which matches what we found above: n+1 vertices, Θ(n²) edges (node len contributes len edges), so Θ(n²) total.

bottomUpCutRodWithCuts + listCuts — reconstructing the cuts

Input size → what’s feasible: same Θ(n²) time as bottomUpCutRod: n ≤ 10⁴ → ≈ 5·10⁷ steps; the extra array cut costs only n+1 more ints.

Knowing the best revenue is often not enough — you need the actual list of cuts. The fix needs no extra asymptotic cost: alongside r[len], also remember cut[len] = the length of the first piece cut in an optimal solution for length len. Then to print the whole solution, repeatedly print cut[n] and jump to the remaining length n - cut[n], until nothing is left.

listCuts — reading the cuts out of the cut table

Input size → what’s feasible: O(n) steps with at most n pieces — instant for any n whose table fits (n ≤ 10⁴ here).

The short procedure below simply walks the cut table: print the first piece cut[left], subtract it from left, repeat until nothing is left. (The players show the finished tables so you can watch only the walk.)

Matrix-chain multiplication

Indexing note. The matrices are A0 … A(n−1), and a list dims of n+1 numbers describes them: matrix At has dims[t] rows and dims[t+1] columns. So 3 matrices need 4 numbers, and neighbouring matrices automatically agree on their shared dimension.

There are Ω(2n) (Catalan-number-many) ways to fully parenthesize a chain of n matrices, so brute force is out. Let m[i][j] = the minimum cost to compute the product AiAi+1⋯Aj. Any optimal parenthesization splits at some point k into (Ai⋯Ak)(Ak+1⋯Aj), and — by a cut-and-paste argument (if either half weren't itself optimal, splicing in a cheaper one would beat the "optimal" whole, a contradiction) — both halves must themselves be optimally parenthesized. The last multiplication multiplies a dims[i] × dims[k+1] result by a dims[k+1] × dims[j+1] result, costing dims[i]·dims[k+1]·dims[j+1]. That gives the split recurrence:

m[i][j] = mini≤k<j { m[i][k] + m[k+1][j] + dims[i]·dims[k+1]·dims[j+1] }, with m[i][i] = 0

How many parenthesizations are there? Count them by recurrence, by the Catalan closed form, and by actually listing them (with their scalar-multiplication costs) — the (AB)C-vs-A(BC) example and a six-matrix chain included.

Why not just recurse directly? (overlapping subproblems, previewed)

Input size → what’s feasible: 3ⁿ⁻¹ calls (measured below): n = 12 → 177,147 calls; n = 15 → ≈ 4.8·10⁶; n = 20 → ≈ 1.2·10⁹ (about 10 s). Use plain recursion only for n ≲ 15.

Coding the split recurrence exactly as written — a plain recursive function with no table — technically works, but it's exponential, for the same reason cutRodNaive was: the same (i,j) range gets asked for over and over from different branches of the recursion.

The exponential blow-up, counted: calls made by the table-free recursion against the number of different (i, j) ranges.

matrixChainOrder + parenthesize

Input size → what’s feasible: n ≤ 500 matrices → (n³−n)/6 ≈ 2.1·10⁷ inner steps (well under 1 s) and n² = 2.5·10⁵ cells per table; n = 2000 → ≈ 1.3·10⁹ steps, too slow for ~1 s.

The DP fix: fill the table by increasing chain length len (so every m[i][k] and m[k+1][j] needed to compute m[i][j] — both strictly shorter chains — is already filled in). Alongside m, record s[i][j] = the split point k that achieved the minimum, so the parenthesization can be reconstructed afterward by parenthesize.

parenthesize — reading the split points out of s

Input size → what’s feasible: O(n) work — at most n leaves and n−1 pairs of parentheses — trivial once the table exists (n ≤ 500 here); recursion depth is at most n−1.

Once s is filled, a few lines rebuild the parenthesization: the split for the whole chain is s[0][n−1]; then recursively do the left part and the right part, wrapping each multi-matrix piece in parentheses.

The Θ(n³) bound, counted: the innermost line runs (n³−n)/6 times, and the tables hold n(n+1)/2 entries.

Elements of dynamic programming

Two properties must BOTH hold for DP to be the right tool:

The same check in code: exhaustive search over a 5-vertex graph shows the halves of a longest simple path are not themselves longest.

matrixChainMemo and memoLookup — the top-down alternative

Input size → what’s feasible: same Θ(n³) as the bottom-up version: n ≤ 500 → ≈ 2.1·10⁷ steps, recursion depth ≤ n; n = 2000 → ≈ 1.3·10⁹ steps, too slow.

The table-free recursion above can be rescued without turning it upside-down: keep the recursive shape, but give every range (i,j) a table entry that starts at ∞ ("not computed yet"). matrixChainMemo (6 lines) sets up the table, and memoLookup (10 lines) is the recursion with a "look before you compute" check on its first line. Each range is computed once, so there are Θ(n²) real computations of O(n) work each: O(n³), the same as bottom-up.

Top-down does the same work as bottom-up, as code: every range computed once, every k-loop run once.

Longest common subsequence

Brute force tries all 2m subsequences of the first string — exponential. Let c[i][j] = the LCS length of the first i letters of x and the first j letters of y (so row 0 and column 0 are the empty prefix, and the i-th letter of x is x[i−1] in Dart). Looking at the last letters of the two prefixes gives the optimal-substructure recurrence:

c[i][j] = c[i-1][j-1] + 1 if x[i−1] = y[j−1], else c[i][j] = max(c[i-1][j], c[i][j-1])

Notice this is different in kind from rod cutting/matrix-chain's recurrences: it rules subproblems in or out based on a condition (do the last letters match?) rather than trying every possible choice.

The recurrence as code, checked against brute force over all 2^m subsequences, and the Θ(mn) size of the table in real numbers.

lcsLength + readLcs

Input size → what’s feasible: m·n ≤ 10⁷ → e.g. two 3000-letter strings = 9·10⁶ cells ≈ 0.1 s; the full c table then costs ≈ 72 MB (8 bytes per cell) plus b, so keep two rows if you only need the length; m = n = 10⁵ → 10¹⁰ cells, too slow.

readLcs — spelling out the subsequence

Input size → what’s feasible: O(m+n) steps — at most 6000 for two 3000-letter strings — trivial next to the table fill.

The length is in c[m][n], but the letters themselves are recovered by starting at the bottom-right cell and following the arrows of b back to the top-left. Only a diagonal arrow ↖ (a matched letter) prints something.

Optimal binary search trees

Keys are k0 … k(n−1), so key kt has probability p[t], and gap dt (the misses landing just before key kt) has probability q[t], for t = 0..n; all 2n+1 probabilities add up to 1. Cost of a tree T: 1 + Σ depthT(kt)·p[t] + Σ depthT(dt)·q[t] (root has depth 0; the leading +1 accounts for the one comparison every search makes at the root). Any subtree spans a contiguous range of keys plus the dummy leaves just outside that range. Use half-open ranges: cost[i][j] is the minimum expected cost for the subtree holding keys ki … kj−1 (so cost[i][i] = q[i] is the "just a dummy leaf" base case), and weight[i][j] is the total probability mass in that range. The key identity is that placing a subtree one level deeper adds exactly weight[i][j] to its cost (since every key/dummy inside gains one level of depth), giving the recurrence (the root is some key kr with i ≤ r < j):

cost[i][j] = mini≤r<j { cost[i][r] + cost[r+1][j] + weight[i][j] }

The weight and cost recurrences as code: weight(i,j) computed directly vs incrementally, the cost of the whole tree vs the cost of the actual tree, and the Θ(n³) step count (versus Θ(n⁴) if weight were recomputed).

optimalBst + listOptimalTree

Input size → what’s feasible: n ≤ 500 keys → n(n+1)(n+2)/6 ≈ 2.1·10⁷ root tries (20,958,500 exactly); n = 2000 → ≈ 1.3·10⁹, too slow — switch to Knuth’s O(n²) version (see the interview bank): n = 5000 → ≈ 2.5·10⁷ steps.

listOptimalTree — listing the optimal tree

Input size → what’s feasible: O(n) steps — one line per node, 2n+1 nodes.

The short procedure below turns the root table into the actual tree: starting from root[0][n], print the key at the top, then recursively do the keys to its left and to its right; an empty key range is a dummy leaf.

Classic interview DP

Beyond the four worked problems above, several DP patterns show up constantly in interviews. Three of the most common get their own animated, custom-input walkthroughs here: a simplified edit distance (insert, delete or replace a letter, each at cost 1), 0/1 knapsack (the contrast case where greedy fails but DP works), and the longest palindromic subsequence (a direct reduction to LCS).

Edit distance

Input size → what’s feasible: m·n ≤ 10⁷ → e.g. two 3000-letter words = 9·10⁶ cells, fine with two rolling rows; m = n = 10⁵ → 10¹⁰ cells, too slow.

0/1 Knapsack

Input size → what’s feasible: n·W ≤ 10⁷ → e.g. n = 1000 items and W = 10⁴; W = 10⁹ is hopeless — the running time is pseudo-polynomial in the value of W, not its number of digits.

Longest palindromic subsequence

Input size → what’s feasible: n ≤ 5000 → n²/2 ≈ 1.25·10⁷ cell updates, O(n) memory with one rolling row; n = 10⁵ → 5·10⁹, too slow.

Quiz

Interview questions

Questions tagged classic are widely reported interview problems that go beyond the worked examples above; the untagged ones test the chapter's own procedures.

Cheat sheet