Dynamic Programming Algorithm (Longest Common Subsequence)

Definition

Dynamic Programming Algorithm (Longest Common Subsequence)

Given two strings $S$ and $T$, the dynamic programming algorithm for the longest common subsequence problem computes the optimum for pairs of prefixes and reuses those results.

Use zero-based indices. For a string $P$, $P[i]$ is the letter at index $i$, and $P[a..b]$ is the substring from index $a$ to index $b$, including both endpoints.

Let $\ell (i,j)$ be the length of an LCS of the prefixes $S[\mathrm{0..}i]$ and $T[\mathrm{0..}j]$.

If one prefix is empty, no non-empty common subsequence is possible:

$$\ell (i,-1)=\ell (-1,j)=0.$$

For non-empty prefixes, compare their last letters:

$$\ell (i,j)=\{\begin{array}{ll}\ell (i-1,j-1)+1& \text{if }S[i]=T[j]\\ \max \{\ell (i,j-1),\ell (i-1,j)\}& \text{if }S[i]\ne T[j]\end{array}$$

Return $\ell (|S|-1,|T|-1)$. Memoisation computes each required state at most once.

Pseudocode

Initialise all memo entries as unknown, then call lcs_rec(|S|-1, |T|-1).

int lcs_rec(int i, int j)
    if i < 0 or j < 0:
        return 0
    if memo[i][j] is known:
        return memo[i][j]
    if S[i] == T[j]:
        memo[i][j] := lcs_rec(i-1, j-1) + 1
    else:
        memo[i][j] := max(lcs_rec(i, j-1), lcs_rec(i-1, j))
    return memo[i][j]

Correctness

Prefix Recurrence

The recurrence computes the exact LCS length for every pair of prefixes.

Proof

Use induction on the sum of the prefix lengths. An empty prefix gives length $0$. All recursive dependencies have smaller total prefix length.

Matching last letters

Assume $S[i]=T[j]$. Appending this common letter to an LCS of the two shorter prefixes gives

$$\ell (i,j)\ge \ell (i-1,j-1)+1.$$

Conversely, take an LCS $X$ of the current prefixes and remove its last letter. The remaining letters occur strictly before the final matched positions in both strings, hence in $S[\mathrm{0..}i-1]$ and $T[\mathrm{0..}j-1]$:

$$|X|-1\le \ell (i-1,j-1)⟹\ell (i,j)\le \ell (i-1,j-1)+1.$$

Both bounds force equality. Thus matching the last letters is at least as good as dropping either one.

Different last letters

Assume $S[i]\ne T[j]$. A common-subsequence alignment cannot use both final positions: both would have to represent its last letter, but the letters differ. Hence every alignment omits at least one final position:

$$\begin{array}{rl}\text{omit }S[i]& ⟹|X|\le \ell (i-1,j),\\ \text{omit }T[j]& ⟹|X|\le \ell (i,j-1).\end{array}$$

This gives the upper bound by their maximum. Conversely, a common subsequence of either smaller prefix pair remains feasible for the current pair. The maximum is therefore also attainable.

Subproblem Reuse

The diagram shows the dependencies of a recursive call. In the mismatch case, both branches can reach the same smaller prefix pair; memoisation avoids computing it twice.

Complexity

With memoisation or bottom-up table filling,

$$\underset{\text{non-empty prefix pairs}}{\underbrace{|S||T|}}\cdot \underset{\text{work per state}}{\underbrace{O(1)}}=O(|S||T|).$$

The time complexity is $O(|S||T|)$ for non-empty inputs; an empty input returns $0$ immediately. The memo table uses $O(|S||T|)$ space, with at most $O(|S|+|T|)$ recursive stack depth.

Bottom-up evaluation can retain only the previous and current rows, reducing auxiliary space to $O(\min \{|S|,|T|\}+1)$ when only the length is required. Without memoisation, the recursion can take exponential time because subproblems reappear.

Examples

Prefix table for abc and ac

Let $S=\text{abc}$ and $T=\text{ac}$. Each entry is the LCS length of its row and column prefixes:

Prefix of S / prefix of T	$\epsilon$	a	ac
$\epsilon$	0	0	0
a	0	1	1
ab	0	1	1
abc	0	1	2

The final letters match, so the final entry is

$$\ell (2,1)=\underset{\text{ab versus a}}{\underbrace{\ell (1,0)}}+1=2.$$

A longest common subsequence is $\text{ac}$.