Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Dynamic Programming Approach

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.

Does the subproblem need to remember which subset of items has already been used, not just a count, a range, or a single position?

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.

Is the subproblem indexed by a node in a tree, filled in from children up to their parent — not a position in a flat sequence at all?

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.

Is the subproblem built from the digits of a single number, needing one extra bit of state for whether the prefix chosen so far still matches that number exactly?

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.

Is a table cell indexed by a position in each of two sequences — comparing two strings (or arrays) against each other position by position?

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.

Does the shared run need to be contiguous — an unbroken block in both sequences — or is skipping around allowed?

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.

Do you need to know how much of the two sequences already lines up, or the true minimum number of edits to turn one into the other?

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.

Is the whole subproblem one contiguous range of a single sequence, decided by trying every point that could split it — not a per-item include-or-skip decision at all?

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.

Is compatibility between the items you're choosing governed by a shared numeric resource that depletes as items are taken, or by a positional/temporal ordering instead?

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."

If it's the shared-capacity branch above: is each item limited to one use, or can the same item be taken more than once?

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.

Down to one sequence, no capacity or interval structure at all — does deciding 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.

Side by side

EntrySubproblem shapeTimeSpaceReach 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