Longest Common Subsequence and Optimal Binary Search Trees Explained

The Longest Common Subsequence Problem

A Subsequence of a string is derived by deleting zero or more characters without changing the order of the remaining characters. The Longest Common Subsequence (LCS) problem asks: given two sequences, find the longest subsequence common to both.

Example:
X = "ABCBDAB"
Y = "BDCABA"

One common subsequence: "BCBA" (length 4)
Another: "BDAB" (length 4)
The LCS in this case has length 4

This problem underlies the diff utility used to compare file versions, DNA sequence comparison in bioinformatics, and plagiarism detection tools, making it one of the most practically significant applications of dynamic programming.

Establishing Optimal Substructure

Let Xᵢ denote the first i characters of string X, and similarly for Yⱼ. The key structural insight considers the last characters of both sequences.

If X[i] == Y[j]:
    the LCS of Xᵢ and Yⱼ extends the LCS of Xᵢ₋₁ and Yⱼ₋₁
    by exactly this matching character

If X[i] ≠ Y[j]:
    the LCS of Xᵢ and Yⱼ is the longer of:
    - the LCS of Xᵢ₋₁ and Yⱼ (drop the last character of X)
    - the LCS of Xᵢ and Yⱼ₋₁ (drop the last character of Y)

This gives the recurrence for c[i][j], the length of the LCS of Xᵢ and Yⱼ:

c[i][j] = 0                              if i == 0 or j == 0
c[i][j] = c[i-1][j-1] + 1                if i,j > 0 and X[i] == Y[j]
c[i][j] = max(c[i-1][j], c[i][j-1])      if i,j > 0 and X[i] ≠ Y[j]

Building the Solution Bottom-Up

LCS-LENGTH(X, Y, m, n):
  let c[0..m][0..n] and b[1..m][1..n] be new tables
  for i = 1 to m:
      c[i][0] = 0
  for j = 0 to n:
      c[0][j] = 0
  for i = 1 to m:
      for j = 1 to n:
          if X[i] == Y[j]:
              c[i][j] = c[i-1][j-1] + 1
              b[i][j] = "diagonal"
          elif c[i-1][j] ≥ c[i][j-1]:
              c[i][j] = c[i-1][j]
              b[i][j] = "up"
          else:
              c[i][j] = c[i][j-1]
              b[i][j] = "left"
  return c, b

Tracing through the earlier example with X = "ABCBDAB" and Y = "BDCABA" fills a table where c[7][6] ultimately holds the value 4, matching the LCS length found by inspection above.

Since the table has Θ(mn) entries and each takes O(1) time to fill given the entries it depends on, the algorithm runs in Θ(mn) time — a dramatic improvement over the exponential number of possible subsequences that a naive brute-force approach would need to examine.

Reconstructing the Actual Subsequence

The auxiliary table b records which case applied at each cell, allowing the actual longest common subsequence, not just its length, to be reconstructed by tracing backward from b[m][n] to the origin, following "diagonal" moves to collect matching characters, and "up" or "left" moves to skip non-matching positions.

Optimal Binary Search Trees: A Different Kind of Optimization

The binary search tree discussed earlier in this series assumes every key is equally likely to be searched. In many real applications, some keys are searched far more frequently than others, and the tree's shape should reflect this: frequently accessed keys should sit closer to the root, minimizing their search cost, even if this means less-frequently accessed keys sit deeper.

Given n distinct keys with known search probabilities p₁, ..., pₙ, the Optimal Binary Search Tree problem asks for the binary search tree structure that minimizes the expected total search cost.

Expected search cost of a tree T:
E[search cost] = Σ (i=1 to n) (depth_T(kᵢ) + 1) · pᵢ

where depth_T(kᵢ) is the depth of key kᵢ in tree T
(root has depth 0, so accessing it costs 1 comparison)

Establishing the Recursive Structure

The key insight, similar in spirit to matrix-chain multiplication discussed earlier in this series, is that an optimal binary search tree over a contiguous range of keys has a recursive structure: whichever key is chosen as the root of a subtree, the keys smaller than it must form the left subtree, and the keys larger than it must form the right subtree, and each of these subtrees must itself be optimal for its respective range and set of probabilities.

Let e[i][j] = expected cost of an optimal BST
              containing keys kᵢ through kⱼ

Let w[i][j] = sum of probabilities pᵢ through pⱼ
              (this accounts for the cost increase of
               adding one more level to every node
               in the subtree, since choosing a root
               increases every descendant's depth by 1)

e[i][j] = min over r (i ≤ r ≤ j) of:
            e[i][r-1] + e[r+1][j] + w[i][j]

Base case: e[i][i-1] = 0  (empty subtree)

The term w[i][j] is added regardless of which root r is chosen, since selecting any node as a subtree's root increases the depth of every other node in that subtree by exactly one level, adding w[i][j] to the total expected cost no matter how the subtree is further structured internally.

Filling the Table Bottom-Up

OPTIMAL-BST(p, n):
  let e[1..n+1][0..n], w[1..n+1][0..n], root[1..n][1..n] be new tables
  for i = 1 to n + 1:
      e[i][i-1] = 0
      w[i][i-1] = 0
  for length = 1 to n:
      for i = 1 to n - length + 1:
          j = i + length - 1
          e[i][j] = infinity
          w[i][j] = w[i][j-1] + p[j]
          for r = i to j:
              t = e[i][r-1] + e[r+1][j] + w[i][j]
              if t < e[i][j]:
                  e[i][j] = t
                  root[i][j] = r
  return e, root

The algorithm proceeds by increasing subtree length, exactly as in matrix-chain multiplication, since e[i][j] depends only on entries involving strictly shorter ranges. With Θ(n²) table entries, each requiring O(n) work to try every possible root, the total running time is Θ(n³), matching matrix-chain multiplication's complexity exactly, a reflection of the structural similarity between the two problems.

Why These Two Problems Illustrate Dynamic Programming's Range

Longest common subsequence and optimal binary search trees, despite solving very different practical problems — string comparison versus data structure optimization — both follow the same fundamental dynamic programming pattern established earlier in this series: identify optimal substructure by considering the last decision made (which characters match, or which key becomes the root), express the solution as a recurrence over subproblems, and fill a table bottom-up in an order that ensures every dependency is already computed. Recognizing this shared pattern across seemingly unrelated problems is the key skill for applying dynamic programming to new problems not yet seen.