This site's Dynamic Programming category holds eleven
entries, and every one of them shares 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 nine questions, walking from the richest state —
a table indexed by an entire subset of items — down to a single running number.
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.
Two of the eight remaining entries build a genuinely two-dimensional table, one axis per
sequence: Longest Common Subsequence 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." If the answer is
yes, go to the next question to pick between the two. 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.
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
and Edit Distance 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 |
| 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 |