This site's Dynamic Programming category holds fourteen
entries. Twelve of them share the same two properties — optimal substructure and overlapping
subproblems — that Longest Common
Subsequence's own Why it works section names as what makes dynamic programming apply at all.
Where they differ, sharply, is subproblem shape: what a table cell is indexed
by, and how far back it has to look to fill itself in. Kadane's Algorithm's own Complexity section states the
range directly: "every other dynamic-programming page on this site needs at least
O(n) space to hold a full table or array for backtracking; Kadane's Algorithm is the
first entry in the category that needs none of it, because each cell only ever depends on the one
immediately before it." This guide is a funnel of ten questions over those twelve, walking from the
richest state — a table indexed by an entire subset of items — down to a single running number.
The thirteenth and fourteenth, Divide
and Conquer DP Optimization and Knuth's
Optimization, are both set aside up front, the same way Choosing a Convex Hull Algorithm sets aside
Convex Hull Trick: neither is a new subproblem shape, each is a speedup bolted onto a transition
shape several of the twelve below already have — a one-dimensional dp[i] = min over j<i of
dp[j] + cost(j,i) for the former, a range-split dp[i][j] = min over k of dp[i][k-1] +
dp[k+1][j] + w(i,j) for the latter — once that transition's optimal predecessor is checked to
be monotonic.
One entry's state is qualitatively richer than every other's: Held–Karp. Its cell, dp[mask][j], is
indexed by an entire bitmask of which waypoints have been visited plus which one the route
currently ends at — 2ⁿ possible subsets, not n positions or
n² range endpoints. Its own opening paragraph calls itself "the first whose subproblem
is indexed by an exponential state... not a range, a count, or a single position the way every other
entry on this page's own guide is" — true of every other entry below. That exponential state is also
why it's the one entry on this page whose complexity, O(n² · 2ⁿ), is still exponential
after the dynamic programming speedup, just a dramatically smaller exponential than the
O(n!) brute force it replaces. If your subproblem doesn't need to track a whole subset,
continue to the next question.
One entry's table isn't shaped like a line or a grid at all: Maximum Weight Independent Set on a Tree.
Its cell is a node's own pair of numbers — its best score with the node included, and its best score
without it — and the usual left-to-right sweep every entry below uses is replaced by a
post-order traversal: every child must be finished before its parent can even start,
because a node's own two numbers are built entirely out of sums over its children's numbers. Its own
Why it works section makes the boundary explicit: "neither formula reads anything about
u's parent or siblings — only its children — which is exactly why a tree makes this
cheap: a node's subtree is a self-contained problem, untouched by anything outside it." That
self-containment is also why it's the cheapest table shape on this page apart from Kadane's running
scalar: a flat O(n) pass, one visit and one combine per node, no exponential state and
no range search. If your subproblem is built from a flat sequence instead, continue to the next
question.
One entry works over a different kind of sequence entirely: Digit DP. Its own opening paragraph calls itself "the first
whose table isn't indexed by a position in an array, a range, a bitmask, or a tree node — it's
indexed by a position in the decimal digits of a single number N, carrying one extra bit
of state no other entry on this page's own guide needs: whether the digits chosen so far still equal
N's own digits exactly, or have already fallen strictly below them." Two parallel tables,
free[pos][r] and tight[pos][r], fill position by position from the last
digit back to the first — and its own Why it works section explains why the extra flag stays cheap:
"being tight at position pos requires every earlier digit to already equal
D[0..pos-1] exactly, so there is only ever one tight path through the whole
computation." If your subproblem doesn't touch a single number's own digits, continue to the next
question.
Three of the nine remaining entries build a genuinely two-dimensional table, one axis per
sequence: Longest Common Subsequence, Longest Common Substring, and Edit Distance. Edit Distance's own opening paragraph calls
itself "a direct generalization" of Longest Common Subsequence, and its Pitfalls section makes the
relationship exact: "Longest Common Subsequence is edit distance with only two of the three edits
allowed, each still costing one... it's the same table, the same backtracking shape, and the same
O(m·n) cost, just with a narrower edit set and a different objective." Longest Common
Substring's own opening paragraph frames its relationship to Longest Common Subsequence the same
way, as "small variations on each other" whose tables "look almost identical" despite one word's
difference in the mismatch rule. If the answer is yes, go to the next question. If no — the
subproblem is built from one sequence, or a set of items with no second string to compare against —
skip ahead to the next question after that.
The match must be one unbroken block, in both strings, back to back: Longest Common Substring. Its own Why it works
section explains the consequence of that one constraint: a mismatch can't carry the better neighbor
forward the way Longest Common Subsequence does, because "a subsequence is still free to skip the
character that didn't match and keep going... a substring has no such freedom," so the cell resets
to exactly 0 instead. That reset breaks the convention every other two-sequence entry
on this page relies on — reading the answer out of the table's bottom-right corner — since the
longest run can end anywhere in the middle of either string; the answer has to be tracked as a
running maximum over every cell as the table fills, not read off one fixed cell at the end. A
20,000-trial sweep found reading the corner disagreeing with the real answer on 93.7% of random
trials, and reusing Longest Common Subsequence's own carry-forward rule wrong on 93.4% — always by
overcounting, since a carried-forward value can only be greater than or equal to a true
reset. Skipping is allowed — the match just needs to appear in order, not touching:
continue to the next question to pick between the two entries that allow it.
Maximize what's already shared, only ever allowed to skip characters (never substitute or
insert): Longest Common
Subsequence. Its recurrence has exactly two cases — extend a match diagonally
(dp[i-1][j-1] + 1) or carry forward the better of dropping one character from either
side (max(dp[i-1][j], dp[i][j-1])) — and its base row and column are all zero, because
"an empty prefix shares nothing with anything." Compute the fewest single-character
edits — insert, delete, and substitute all count, each as one edit: Edit Distance. Its own Why it works section explains why
its base case looks different from Longest Common Subsequence's: "the table here needs a base row
and column of actual counts, not the all-zero border Longest Common Subsequence's table
had... here, an empty prefix still costs something to reach" (turning i characters into
nothing costs i deletes, and vice versa). Both fill an (m+1)×(n+1) table in
O(m·n), both can drop to O(min(m,n)) space if only the number is needed
(not the reconstructed characters/edit script), and both entries name the identical caveat about
that trade: the two-row version can no longer backtrack.
One entry doesn't fit the two-sequence shape above or the per-item questions below: Matrix Chain Multiplication. Its cell,
dp[i][j], answers "what's the cheapest way to multiply matrices i through
j as one group" — indexed by a contiguous range of one sequence, filled by
trying every internal split point k and keeping the best:
dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j]. Its own Complexity
section names the consequence directly: that extra split-point search costs O(n³)
overall, "a real step up from every other entry in this category," since Longest Common Subsequence,
Longest Common Substring, and Edit Distance all fill an equally two-dimensional table but spend only
O(1) work per cell. If your subproblem instead asks a yes-or-no question about one item
at a time, continue to the next question.
Two more entries ask a "take it or skip it" question per item — the same shape, in fact: Weighted Interval Scheduling's own Why it
works section says every activity "faces exactly one yes-or-no question, the same shape 0/1 Knapsack's own recurrence asks of every item." What splits
them apart is what a taken item competes for. A shared numeric budget — weight, cost,
whatever a fixed capacity limits — where taking one item leaves strictly less room for the
rest: 0/1 Knapsack. Its table is genuinely
two-dimensional, dp[i][w] indexed by item count and remaining capacity, with
dp[i][w] = max(dp[i-1][w], valuei + dp[i-1][w - weighti]) when an
item fits. A positional or temporal ordering — item i is only compatible with
items that end before i starts, no numeric budget involved at all: Weighted Interval Scheduling. Its table
collapses to one dimension, dp[i] = max(dp[i-1], weighti +
dp[p(i)]), where p(i) — the latest earlier compatible activity — is
found by binary search over the finish-time-sorted order rather than read off a numeric axis.
Knapsack's own Complexity section flags a real consequence of the capacity axis: its O(n ·
W) bound depends on the numeric magnitude of the capacity, not just the item count, making it
pseudo-polynomial; Weighted Interval Scheduling's O(n log n) depends
only on the number of activities, "never on the numeric magnitude of any start or end time —
genuinely polynomial, not pseudo-polynomial."
Each item usable once: 0/1 Knapsack, as
above. Each item usable any number of times, supply unlimited: Unbounded Knapsack. Its own opening paragraph frames
itself as 0/1 Knapsack's compressed single row with one loop direction flipped: fill the capacity
loop ascending instead of descending and a cell can read a value the same item's own pass
already improved earlier in that same row — reuse falls out for free, "a bug 0/1 Knapsack's own
Pitfalls section warns against, done on purpose." The two share the identical recurrence shape
otherwise, one term shorter for Unbounded Knapsack since there's no "skip vs. take, given what's
already decided" distinction left to make — an item is either affordable at a given capacity or it
isn't, independent of anything already chosen. That drops the axis 0/1 Knapsack needs its full
O(n · W) table to preserve for backtracking; Unbounded Knapsack reconstructs an actual
optimal combination from the compressed O(W) row alone, no space trade-off at all.
dp[i] ever need to compare against an arbitrary earlier index, or only the one right
before it?The last two entries both define dp[i] as "the best answer for a chain ending
exactly at index i," scanned once left to right — but they need a different amount of
history to fill that cell in. Extending the chain at i depends on which earlier
index it connects to, potentially any of them: Longest Increasing Subsequence. Its direct
recurrence "checks every earlier index j < i: if arr[j] < arr[i], the
run ending at j can be extended" — an O(n²) table by default, though its
own hook is that the fastest route "isn't really a DP recurrence at all, it's binary search wearing a
different hat": patience sorting keeps only the best (smallest) ending value per run length in a
tails array, cutting the cost to O(n log n) without ever filling a 2D
table. Extending the chain at i only ever depends on the single cell
dp[i-1], nothing earlier: Kadane's
Algorithm, whose recurrence is just dp[i] = max(a[i], dp[i-1] + a[i]) — extend the
running subarray or start fresh. Because no cell ever reads anything but its immediate predecessor,
"the whole array of intermediate values collapses to one running variable" — O(1)
space, no table, no array, not even the O(n) every other entry on this page needs at
minimum.
| Entry | Subproblem shape | Time | Space | Reach for it when |
|---|---|---|---|---|
| Held–Karp | exponential, subset of items visited × current position | O(n²·2ⁿ) | O(n·2ⁿ) | cheapest route/order visiting every item exactly once |
| Maximum Weight Independent Set on a Tree | tree, one cell per node, include/exclude combined child-before-parent | O(n) | O(n) table + O(h) recursion | highest-value subset of tree nodes, no two directly connected |
| Digit DP | digit position × remaining target, plus a tight/free flag | O(D·S) | O(D·S), compressible to O(S) | count integers up to N sharing a digit-level property |
| Longest Common Subsequence | 2D, two string prefixes, skip-only | O(m·n) | O(m·n) full; O(min(m,n)) length-only | maximize matched characters between two sequences |
| Longest Common Substring | 2D, two string prefixes, contiguous-only (reset on mismatch) | O(m·n) | O(m·n) full; O(min(m,n)) — keeps the substring, unlike LCS | longest unbroken shared run between two sequences |
| Edit Distance | 2D, two string prefixes, insert/delete/substitute | O(m·n) | O(m·n) full; O(min(m,n)) distance-only | minimum-cost transform of one sequence into another |
| Matrix Chain Multiplication | 2D, contiguous range [i,j] of one sequence, split at internal k | O(n³) | O(n²) | cheapest grouping to multiply an associative chain |
| 0/1 Knapsack | 2D, item count × remaining capacity | O(n·W), pseudo-polynomial | O(n·W) full; O(W) single-row (loses backtrack) | subset of items under a shared numeric budget |
| Unbounded Knapsack | 1D, remaining capacity only, items reusable | O(n·W), pseudo-polynomial | O(W), backtrack included at no extra cost | maximize value under a shared budget, unlimited item supply |
| Weighted Interval Scheduling | 1D array + binary-searched predecessor | O(n log n) | O(n) | weighted items compatible by position/time, no shared capacity |
| Longest Increasing Subsequence | 1D, each cell may need any earlier one | O(n²) direct; O(n log n) patience sorting | O(n) | longest ordered chain extracted from one sequence |
| Kadane's Algorithm | running scalar, no table | O(n) | O(1) | best contiguous run in one sequence, extend-or-restart |