Every algorithm on this site so far has been greedy (always take the locally best option and never look back — Kruskal's algorithm, Prim's algorithm), a search over a fixed structure (binary search, the trees), or a direct traversal (BFS, DFS). This one is the site's first entry in a different family entirely: dynamic programming — solve a small version of the problem, save the answer, and reuse it instead of recomputing it every time a bigger version needs it. The problem itself is simple to state: given two sequences, find the longest sequence that appears in both, in order, but not necessarily contiguously. "ABCBDAB" and "BDCABA" don't share a long unbroken run anywhere, but they do share "BCBA" — B, C, B, A each show up in that order in both strings, with other characters allowed to sit between them.
Two fixed strings, A = "AGGTAB" and B = "GXTXAYB" — a standard textbook pair
chosen because their longest common subsequence, "GTAB", isn't obvious just from staring at
the strings. Press Step or Run to watch the table fill in, one cell at a
time: each cell dp[i][j] holds the LCS length of the first i characters of
A against the first j characters of B. Once the table is full, the
demo backtracks from the bottom-right corner to the top-left, reconstructing the actual matched
characters — watch the highlighted path and the two strings below light up in sync.
Switch the mode dropdown to space-optimized to see the two-row trick from Pitfalls
run for real: instead of a full (m+1)×(n+1) table, only a prev row and a
curr row ever exist at once, and the stats line tracks exactly how many cells that saves.
The trade is real too — this mode reports the LCS length only, never the subsequence itself,
because once a row is overwritten there's nothing left to backtrack through.
Switch it to top-down (memoized recursion) to see the other fix Pitfalls names: the
same recurrence, called as ordinary recursion starting from dp[m][n], with each answer
cached in a map keyed by (i, j) the first time it's computed. Unfilled cells show as
· until the recursion actually reaches them — watch that most of the table never lights up
at all: this mode still reconstructs the full subsequence (the memo is a complete substitute for the
table), but it does it having computed strictly fewer cells than the version above.
The recurrence has exactly two cases, and both are forced by what "longest common subsequence"
means. If the two current characters match — A[i-1] === B[j-1] — then the best move is
always to use that match: it can never hurt to include a character both strings offer for free, so
dp[i][j] = dp[i-1][j-1] + 1, one better than whatever the LCS was before either string had
this character. If they don't match, the LCS of the two prefixes has to come from dropping one
character or the other — either "ignore A's last character" (dp[i-1][j]) or
"ignore B's last character" (dp[i][j]... rather dp[i][j-1]) — and
since dropping a character can only ever lose ground, the right answer is whichever of those two was
already better: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
That recurrence only works because of two properties dynamic programming always needs.
Optimal substructure: the best answer to the whole problem is built directly out of
best answers to smaller versions of the same problem — there's no case where using a suboptimal
sub-answer could somehow help. Overlapping subproblems: a plain recursive
implementation of that same recurrence, with no table, would recompute dp[i-1][j-1] from
scratch every time it's needed — and it's needed by many different call paths, since
dp[i][j]'s two neighbors dp[i-1][j] and dp[i][j-1] both depend on
it. Filling the table bottom-up (or caching top-down recursion, "memoization") means each of the
(m+1)(n+1) cells gets computed exactly once.
Builds the table bottom-up, then walks it backward from the last cell to recover the actual characters — not just the length:
function longestCommonSubsequence(a, b) {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// backtrack from the bottom-right corner to recover the characters, not just the count
let i = m, j = n;
const chars = [];
while (i > 0 && j > 0) {
if (a[i - 1] === b[j - 1]) {
chars.push(a[i - 1]);
i--; j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
chars.reverse();
return { length: dp[m][n], subsequence: chars.join('') };
}The naive recursive version — no table — is exponential, not just "a bit slower."
Translate the recurrence directly into a recursive function with no memoization and every call to
lcs(i, j) that isn't a base case makes up to two more recursive calls, each of which can
branch again. The call tree for two length-n strings can reach O(2^n) calls,
even though there are only O(n²) distinct subproblems — the entire cost of the
naive version is repeating work that's already been done. The fix isn't a smarter algorithm, it's just
remembering answers: a table (this page's approach) or a cache keyed by (i, j) on top of
the exact same recursion (top-down memoization) both turn the same exponential tree into the same
O(m·n) worst case, computing each cell once.
Top-down memoization can compute strictly fewer cells than filling the whole table — but only
sometimes, and it's worth checking rather than assuming. Bottom-up fills every one of the
(m+1)(n+1) cells unconditionally, in a fixed order, whether the final answer needs each one
or not. Top-down starts at dp[m][n] and only recurses into a neighbor when the recurrence
actually asks for it — a diagonal match short-circuits straight past the other two neighbors a mismatch
would need. Try it live above by switching to top-down mode: on this page's own
6×7 example, it computes only 32 of the 56 possible cells (13 of those 32 lookups are
cache hits reusing an already-computed neighbor, not new work) — 24 cells the bottom-up table fills that
this particular recursion never actually needed. That saving is a property of this input, not a
guarantee: re-run the same check against two strings that share no characters at all (checked separately,
not shown in the demo above) and top-down touches 48 of the resulting 49 cells — every cell except
dp[0][0], which is only ever reached by a diagonal step out of dp[1][1], and
that step only happens when the strings' very first characters match. Worst case, top-down's cell count
converges on bottom-up's; what it buys is doing less work exactly when a match makes less work
available, never more work than bottom-up would do.
When more than one longest common subsequence exists, backtracking only recovers one of
them — not "the" answer, an answer. On a tie (dp[i-1][j] === dp[i][j-1]), this
page's backtrack step always prefers moving up over moving left; a version that broke the tie the other
way would walk a different path through the table and could return a different string of the same
length. The length the table produces is never ambiguous — but if the exact characters matter,
know that the reconstruction step made an arbitrary choice at every tie, not a uniquely forced one.
This table costs real memory, and there's a cheaper option if you only need the length.
Computing dp[i][j] only ever looks at row i-1 and the current row i
— once row i-1 is done, nothing before it is read again. That means the full
O(m·n) table above can be trimmed to two rows (or one, updated carefully in place),
dropping space to O(min(m, n)). The catch: backtracking to recover the actual subsequence,
the way this page's demo does, needs the full table to walk back through — the two-row trick only works
if the length alone is the answer you need. Try it live above by switching to
space-optimized mode: on this page's own 6×7 example, that's 16 cells kept at any
moment instead of 56 for the full table, a real difference even at this tiny scale.
Time: O(m·n) — one constant-time decision per cell, (m+1)(n+1)
cells total. Space: O(m·n) for the full table (needed to reconstruct the
subsequence), or O(min(m, n)) if only the length is needed — see Pitfalls above.
Longest common subsequence is the algorithm underneath diff and git diff
(the "unchanged" lines of two files are their LCS; everything else is shown as added or removed), and
the same idea generalized to edit costs (insert/delete/substitute, not just skip) is
edit distance. Both fill a table indexed by two string
prefixes; the 0/1 knapsack problem is dynamic programming with a
differently-shaped table — items and capacity instead of two strings — worth a look for how far the same
"solve every smaller subproblem once" idea stretches.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.