Sequence Alignment & LCS

How similar are two strings? algorithm and altruistic share the letters a, l, t, i, c in order, and that shared string, the longest common subsequence, is one of the most useful measures of similarity in computing. It underlies the diff utility, version-control merges, and (with a change of cost function) the alignment of DNA and protein sequences in computational biology.¹ This lesson develops the LCS dynamic program in full, then shows that edit distance is the same dynamic program with the costs rearranged.

The problem

A subsequence of a string is what remains after deleting zero or more characters, keeping the rest in their original order. It need not be contiguous: ace is a subsequence of abcde, but aec is not. Given two strings $X=x_1{x}_2\cdots x_m$ and $Y=y_1{y}_2\cdots y_n$, a common subsequence is a string that is a subsequence of both, and we want a longest one.

A common subsequence is a set of order-preserving matches threading the two strings: the matched letters appear in both, left to right, though the gaps between them differ.

A brute-force search is hopeless: $X$ has $2^m$ subsequences, and checking each against $Y$ gives $\Theta (n{2}^m)$. We need the recipe, and it pays to follow it literally. The DP recipe runs through fixed steps: (0) simplify the goal, (1) define the subproblems and notation, (2) write the DP equations, (3) prove them correct by induction, (4) turn them into iterative pseudocode, (5) return to the original goal, then analyze. We walk LCS through those steps verbatim.

Step 0–1: Simplify the goal, define the subproblem

Simplify first. Computing the string drags around bookkeeping; computing its length is cleaner. So we first solve for the LCS length, then recover an actual subsequence in a cheap second pass (Step 5). With that simplification, the decisive move, which recurs across all sequence DPs, is to index subproblems by prefixes of the two strings. Write $A=X$ and $B=Y$ for the two inputs.

The answer we want is $\mathrm{OPT}(m,n)$. There are $(m+1)(n+1)$ subproblems, one per pair of prefix lengths $0\le i\le m$ and $0\le j\le n$.

Step 2: The DP equations

Now apply optimal substructure by looking at the last characters, $A[i]$ and $B[j]$.² Write the recurrence as a single $\max$ over three cases, plus a base case:

Read the three branches as moves on the prefixes:

• Case 1 drops $A[i]$: an LCS of $A[\mathrm{1..}i-1]$ and $B[\mathrm{1..}j]$ is a common subsequence of $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$, so $\mathrm{OPT}(i,j)\ge \mathrm{OPT}(i-1,j)$.
• Case 2 drops $B[j]$ symmetrically, so $\mathrm{OPT}(i,j)\ge \mathrm{OPT}(i,j-1)$.
• Case 3 fires only when $A[i]=B[j]$: the shared character $c=A[i]=B[j]$ can end an optimal LCS, so we append it to the best LCS of the strictly shorter prefixes, giving $\mathrm{OPT}(i,j)\ge \mathrm{OPT}(i-1,j-1)+1$.

Why exactly these three? Because every common subsequence of $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$ falls into one of three shapes: it ignores $A[i]$ (case 1), ignores $B[j]$ (case 2), or uses both as a final match (case 3, possible only if $A[i]=B[j]$). The $\max$ over the applicable cases is the longest of them. When $A[i]\ne B[j]$, only cases 1 and 2 apply, and the recurrence collapses to $\max \left(\mathrm{OPT}(i-1,j),\mathrm{OPT}(i,j-1)\right)$.

Each entry depends only on its left, upper, and upper-left neighbors, so filling the table row by row, left to right (or column by column) respects every dependency. The same three-neighbour stencil drives every sequence DP below: only the labels on the arrows change.

Step 3: Correctness by induction on $i+j$

Step 4: Iterative pseudocode

The equations are non-circular, since every entry reads strictly smaller prefixes, so they convert directly into a bottom-up table fill. Allocate $\mathrm{OPT}[\mathrm{0..}m][\mathrm{0..}n]$, zero the border, then sweep:

Every cell costs $\Theta (1)$, so the fill is $\Theta (mn)$.

The DP table, filled

Take $A=\text{BDCAB}$ and $B=\text{ABCB}$. We build the $(m+1)\times (n+1)$ table of $\mathrm{OPT}(i,j)$ values. Row $0$ and column $0$ are all zero (empty prefix); every other cell is filled by the recurrence. The shaded diagonal steps mark the matches that build the answer, and the red arrows trace the reconstruction walk (Step 5) backwards from the corner.

The bottom-right entry reads $\mathrm{OPT}(5,4)=3$: the longest common subsequence of BDCAB and ABCB has length $3$, namely BCB (the only one here, though in general there may be ties). The arrows enter each shaded match cell diagonally (emitting B, then C, then B, read from the corner upward) and step straight up or left through non-match cells, exactly as the reconstruction below prescribes.

Step 5: Reconstructing the subsequence

The table gives the length; this is where the Step 0 simplification is paid back. In a second pass we walk backwards from $\mathrm{OPT}(m,n)$, undoing the recurrence. At cell $(i,j)$: if $A[i]=B[j]$, that character belongs to the LCS — emit it and step diagonally to $(i-1,j-1)$ (case 3); otherwise move to whichever neighbor, up or left, holds the larger value (the one the $\max$ of cases 1 and 2 chose).

The walk takes one step toward the origin each call, so it runs in $O(m+n)$ time, cheap compared with building the table.

Trace it on the worked table above, starting at $(5,4)$ with value $3$. The red arrows in the figure are this walk:

• $(5,4)$: $A[5]=\text{B}=B[4]$, a match. Emit B, step to $(4,3)$.
• $(4,3)$: $A[4]=\text{A}\ne \text{C}=B[3]$. Compare the up neighbour $\mathrm{OPT}(3,3)=1$ against the left neighbour $\mathrm{OPT}(4,2)=1$; the tie breaks upward, step to $(3,3)$.
• $(3,3)$: $A[3]=\text{C}=B[3]$, a match. Emit C, step to $(2,2)$.
• $(2,2)$: $A[2]=\text{D}\ne \text{A}=B[2]$. Up neighbour $\mathrm{OPT}(1,2)=1$ ties left neighbour $\mathrm{OPT}(2,1)=0$; step up to $(1,2)$.
• $(1,2)$: $A[1]=\text{B}=B[2]$, a match. Emit B, step to $(0,1)$.
• $(0,1)$: $i=0$, stop.

The emitted characters, corner-first, are B, C, B; reversed into forward order they read BCB — the length-$3$ LCS the corner promised. The tie-break rule (up before left) is arbitrary; the other choice would recover an equally long subsequence, and a longest common subsequence need not be unique.

Running time and space

The table has $(m+1)(n+1)$ entries. Filling one costs a character comparison and a $\max$ of at most three previously-computed neighbours, all $\Theta (1)$. Summing over the fill,

and the border initialization adds only $\Theta (m+n)$, which $\Theta (mn)$ absorbs. The reconstruction pass is $O(m+n)$, also absorbed. LCS therefore runs in $\Theta (mn)$ time — a decisive improvement over the $\Theta (n{2}^m)$ brute force, and for two length-$1000$ strings the difference is a million cell updates against roughly $10^{300}$ subsequence checks.

Space is $\Theta (mn)$ for the full table, but the recurrence reads only the current row and the one directly above it. Keeping two length-$(n+1)$ rows and swapping them after each $i$ (a rolling array) drops the footprint to $\Theta (n)$, and choosing the shorter string as the inner axis makes it $\Theta (\min (m,n))$.

The catch is universal to this trick: collapsing the table erases the information the traceback needs, so the two-row version yields only the length, never the subsequence itself. Recovering the actual alignment in linear space is possible — Hirschberg's divide-and-conquer refinement does it in $\Theta (mn)$ time and $\Theta (\min (m,n))$ space³ — but that machinery is a topic for later.

from typing import Sequence, TypeVar

Element = TypeVar("Element")

def lcs_length(left: Sequence[Element], right: Sequence[Element]) -> int:
  """
    Length of a longest common subsequence of `left` and `right`.\n
    Fills the full (m+1) x (n+1) prefix table and reports the corner.\n
  """
  rows: int = len(left)
  cols: int = len(right)

  # table[i][j] = LCS length of left[:i] and right[:j]; border rows/cols are 0
  # because an empty prefix shares nothing.
  table: list[list[int]] = [[0 for _ in range(cols + 1)] for _ in range(rows + 1)]

  for i in range(1, rows + 1):
    for j in range(1, cols + 1):
      if left[i - 1] == right[j - 1]:
        # case 3: extend the diagonal by the shared final element.
        table[i][j] = table[i - 1][j - 1] + 1
      else:
        # cases 1, 2: drop one side, keep the longer survivor.
        table[i][j] = max(table[i - 1][j], table[i][j - 1])

  return table[rows][cols]

def lcs(left: Sequence[Element], right: Sequence[Element]) -> list[Element]:
  """
    A longest common subsequence itself, as a list of elements.\n
    Builds the same table, then walks backwards from the bottom-right corner:\n
    a match emits its element and steps diagonally; otherwise it follows the\n
    neighbour the max chose. Ties are broken toward the upper neighbour, so the\n
    result is one valid LCS (there may be several of equal length).\n
  """
  rows: int = len(left)
  cols: int = len(right)

  # empty-prefix borders are 0; interior cells are filled below.
  table: list[list[int]] = [[0 for _ in range(cols + 1)] for _ in range(rows + 1)]

  # fill the prefix table: diagonal +1 on a match, else the longer drop.
  for i in range(1, rows + 1):
    for j in range(1, cols + 1):
      if left[i - 1] == right[j - 1]:
        table[i][j] = table[i - 1][j - 1] + 1
      else:
        table[i][j] = max(table[i - 1][j], table[i][j - 1])

  # walk back from the corner, emitting matches and following the max choice.
  result: list[Element] = []
  row, col = rows, cols
  while row > 0 and col > 0:
    if left[row - 1] == right[col - 1]:
      result.append(left[row - 1])
      row -= 1
      col -= 1
    elif table[row - 1][col] >= table[row][col - 1]:
      row -= 1
    else:
      col -= 1

  # the walk emits corner-to-origin, so flip back to forward order.
  result.reverse()
  return result

from typing import Sequence, TypeVar

Element = TypeVar("Element")

def lps_length(sequence: Sequence[Element]) -> int:
  """
    Length of a longest palindromic subsequence of `sequence`.\n
    Fills the substring table over spans of increasing length.\n
  """
  count: int = len(sequence)
  if count == 0:
    return 0

  # table[i][j] = LPS length of sequence[i..j]; single elements are length 1.
  table: list[list[int]] = [[0 for _ in range(count)] for _ in range(count)]
  for index in range(count):
    table[index][index] = 1

  for span in range(2, count + 1):
    for low in range(count - span + 1):
      high: int = low + span - 1
      if sequence[low] == sequence[high]:
        # endpoints pair off; span 2 has no interior, so guard the inner read.
        inner: int = table[low + 1][high - 1] if span > 2 else 0
        table[low][high] = inner + 2
      else:
        table[low][high] = max(table[low + 1][high], table[low][high - 1])

  return table[0][count - 1]

def lps(sequence: Sequence[Element]) -> list[Element]:
  """
    A longest palindromic subsequence itself, as a list of elements.\n
    Builds the same table, then walks inward from the (0, n-1) corner: matching\n
    endpoints are emitted on both sides; otherwise it follows the longer\n
    neighbour. The two halves are stitched around the (possibly empty) centre.\n
  """
  count: int = len(sequence)
  if count == 0:
    return []

  table: list[list[int]] = [[0 for _ in range(count)] for _ in range(count)]
  for index in range(count):
    table[index][index] = 1

  for span in range(2, count + 1):
    for low in range(count - span + 1):
      high: int = low + span - 1
      if sequence[low] == sequence[high]:
        inner: int = table[low + 1][high - 1] if span > 2 else 0
        table[low][high] = inner + 2
      else:
        table[low][high] = max(table[low + 1][high], table[low][high - 1])

  # Collect the left half forward and the right half reversed, then join.
  left_half: list[Element] = []
  right_half: list[Element] = []
  low: int = 0
  high: int = count - 1
  while low < high:
    if sequence[low] == sequence[high]:
      left_half.append(sequence[low])
      right_half.append(sequence[high])
      low += 1
      high -= 1
    elif table[low + 1][high] >= table[low][high - 1]:
      low += 1
    else:
      high -= 1

  centre: list[Element] = [sequence[low]] if low == high else []
  right_half.reverse()
  return left_half + centre + right_half

from bisect import bisect_left
from typing import Sequence, TypeVar

from comparable import Comparable

Element = TypeVar("Element", bound=Comparable)

def lis_length_quadratic(sequence: Sequence[Element]) -> int:
  """
    Length of a longest strictly increasing subsequence, in O(n^2).\n
    `best_ending[i]` is the LIS length finishing at index `i`; each entry looks\n
    back at every smaller predecessor and extends the best of them.\n
  """
  count: int = len(sequence)
  if count == 0:
    return 0

  # best_ending[i] = LIS length finishing at i; extend the best smaller run.
  best_ending: list[int] = [1 for _ in range(count)]
  for index in range(1, count):
    for earlier in range(index):
      if sequence[earlier] < sequence[index]:
        best_ending[index] = max(best_ending[index], best_ending[earlier] + 1)

  return max(best_ending)

def lis_length(sequence: Sequence[Element]) -> int:
  """
    Length of a longest strictly increasing subsequence, in O(n log n).\n
    `tails[k]` holds the smallest tail seen for an increasing run of length\n
    `k + 1`; binary search places each element, and the final length of\n
    `tails` is the answer.\n
  """
  tails: list[Element] = []
  for value in sequence:
    position: int = bisect_left(tails, value)
    if position == len(tails):
      tails.append(value)
    else:
      # value can end a length-(position+1) run with a smaller tail.
      tails[position] = value
  return len(tails)

def lis(sequence: Sequence[Element]) -> list[Element]:
  """
    A longest strictly increasing subsequence itself, in O(n log n).\n
    Runs the patience method while recording, for each placed element, the\n
    index of its predecessor in the chain, then walks the links back from the\n
    final element of the longest run.\n
  """
  count: int = len(sequence)
  if count == 0:
    return []

  # tail_index[k] = index in `sequence` of the current smallest tail of a
  # length-(k+1) run. predecessor[i] = index chained before i, or -1.
  tail_values: list[Element] = []
  tail_index: list[int] = []
  predecessor: list[int] = [-1 for _ in range(count)]

  for index in range(count):
    value: Element = sequence[index]
    position: int = bisect_left(tail_values, value)

    # link each element to the tail of the run it extends.
    if position > 0:
      predecessor[index] = tail_index[position - 1]

    # start a new longest run, or lower the tail of an existing length.
    if position == len(tail_values):
      tail_values.append(value)
      tail_index.append(index)
    else:
      tail_values[position] = value
      tail_index[position] = index

  # walk the predecessor chain back from the tail of the longest run.
  result: list[Element] = []
  cursor: int = tail_index[-1]
  while cursor != -1:
    result.append(sequence[cursor])
    cursor = predecessor[cursor]

  result.reverse()
  return result

from typing import Sequence, TypeVar

Element = TypeVar("Element")

def distinct_subsequences(
  source: Sequence[Element],
  target: Sequence[Element],
) -> int:
  """
    Number of distinct subsequences of `source` that equal `target`.\n
    Counts placements by sweeping the prefix table; positions of repeated\n
    target elements are summed, so identical subsequences are not double\n
    counted.\n
  """
  rows: int = len(source)
  cols: int = len(target)

  # count[i][j] = subsequences of source[:i] equal to target[:j]. The empty
  # target is matched once by every source prefix (the empty pick).
  count: list[list[int]] = [[0 for _ in range(cols + 1)] for _ in range(rows + 1)]
  for i in range(rows + 1):
    count[i][0] = 1

  for i in range(1, rows + 1):
    for j in range(1, cols + 1):
      # ways that skip source[i-1] entirely.
      count[i][j] = count[i - 1][j]
      if source[i - 1] == target[j - 1]:
        # plus ways that use source[i-1] to cover target[j-1].
        count[i][j] += count[i - 1][j - 1]

  return count[rows][cols]

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

The same machine: edit distance

Edit distance (the Levenshtein distance) asks the closely related question: what is the minimum number of single-character insertions, deletions, and substitutions that transform $A$ into $B$?⁴ It is the cost model behind spell-checkers and diff, and it is structurally identical to LCS.

Again we look at the last characters. If $A[i]=B[j]$, they need no edit and we align them for free. Otherwise we make one of three moves (delete $A[i]$, insert $B[j]$, or substitute $A[i]\to B[j]$), each at cost $1$, and recurse on the correspondingly shorter prefixes:

The base cases say it: turning a length-$i$ prefix into the empty string costs $i$ deletions, and building a length-$j$ prefix from nothing costs $j$ insertions.

It is the same three-neighbour stencil as LCS — only the arrow labels change. The diagonal is free on a match and costs $1$ to substitute; a step down deletes $A[i]$, a step right inserts $B[j]$, each at cost $1$. We take the cheapest incoming move instead of the longest:

Filled on a small pair, the table looks just like the LCS one but now minimizes. Take $A=\text{CAT}$ and $B=\text{CARS}$: the shaded diagonal marks the free matches, and the corner reports the answer.

Reading the corner, $D(3,4)=2$. The traceback recovers the alignment itself, walking corner to origin and reading each step as the edit that produced it:

• $(3,4)$ value $2$: the left neighbour $D(3,3)=1$ is one cheaper, so this step is an insertion of $B[4]=\text{S}$. Move left to $(3,3)$.
• $(3,3)$ value $1$: $A[3]=\text{T}\ne \text{R}=B[3]$, and the upper-left $D(2,2)=0$ is the cheapest source, so this is a substitutionT $\to$ R. Move diagonally to $(2,2)$.
• $(2,2)$ value $0$: $A[2]=\text{A}=B[2]$, a free match. Move diagonally to $(1,1)$.
• $(1,1)$ value $0$: $A[1]=\text{C}=B[1]$, a free match. Move to $(0,0)$ and stop.

Read forward, the alignment is: keep C, keep A, substitute T $\to$ R, insert S — turning CAT into CARS in the promised two edits. The match cells on the diagonal ($\text{C}$ and $\text{A}$) copy the upper-left value unchanged, the same LCS diagonal step, but counting saved edits instead of matched characters.

The fill is the LCS loop with $\min$ in place of $\max$ and the borders seeded to the prefix lengths rather than zeros:

Every cell is still $\Theta (1)$, so the fill is $\Theta (mn)$, and the alignment is recovered by the same corner-to-origin traceback as LCS.

from typing import NamedTuple, Sequence, TypeVar

Element = TypeVar("Element")

class Edit(NamedTuple):
  """
    One step of an alignment script: the operation and the elements it acts on.\n
    `operation` is one of "match", "substitute", "delete", "insert"; for a\n
    delete `target` is None, for an insert `source` is None.\n
  """
  operation: str
  source: object
  target: object

def edit_distance(source: Sequence[Element], target: Sequence[Element]) -> int:
  """
    Minimum number of insert/delete/substitute edits taking `source` to\n
    `target`. Fills the full prefix table and reports the corner.\n
  """
  rows: int = len(source)
  cols: int = len(target)

  # distance[i][j] = edits to turn source[:i] into target[:j]. Borders count
  # a run of deletions (empty target) or insertions (empty source).
  distance: list[list[int]] = [[0 for _ in range(cols + 1)] for _ in range(rows + 1)]
  for i in range(rows + 1):
    distance[i][0] = i
  for j in range(cols + 1):
    distance[0][j] = j

  # fill: free on a match, else 1 + cheapest of delete / insert / substitute.
  for i in range(1, rows + 1):
    for j in range(1, cols + 1):
      if source[i - 1] == target[j - 1]:
        distance[i][j] = distance[i - 1][j - 1]
      else:
        distance[i][j] = 1 + min(
          distance[i - 1][j],      # delete source[i-1]
          distance[i][j - 1],      # insert target[j-1]
          distance[i - 1][j - 1],  # substitute
        )

  return distance[rows][cols]

def edit_script(
  source: Sequence[Element],
  target: Sequence[Element],
) -> list[Edit]:
  """
    A minimum-length sequence of edits transforming `source` into `target`.\n
    Builds the same table, then walks backwards from the corner, preferring a\n
    free match, then substitute, then delete, then insert. The returned list is\n
    in forward (left-to-right) order; its non-match steps number exactly the\n
    edit distance.\n
  """
  rows: int = len(source)
  cols: int = len(target)

  # border rows/cols cost a run of deletions or insertions.
  distance: list[list[int]] = [[0 for _ in range(cols + 1)] for _ in range(rows + 1)]
  for i in range(rows + 1):
    distance[i][0] = i
  for j in range(cols + 1):
    distance[0][j] = j

  # fill: free on a match, else 1 + cheapest of delete / insert / substitute.
  for i in range(1, rows + 1):
    for j in range(1, cols + 1):
      if source[i - 1] == target[j - 1]:
        distance[i][j] = distance[i - 1][j - 1]
      else:
        distance[i][j] = 1 + min(
          distance[i - 1][j],
          distance[i][j - 1],
          distance[i - 1][j - 1],
        )

  # walk back from the corner, preferring match, substitute, delete, insert.
  script: list[Edit] = []
  row, col = rows, cols
  while row > 0 or col > 0:
    if (
      row > 0
      and col > 0
      and source[row - 1] == target[col - 1]
      and distance[row][col] == distance[row - 1][col - 1]
    ):
      script.append(Edit("match", source[row - 1], target[col - 1]))
      row -= 1
      col -= 1
    elif (
      row > 0
      and col > 0
      and distance[row][col] == distance[row - 1][col - 1] + 1
    ):
      script.append(Edit("substitute", source[row - 1], target[col - 1]))
      row -= 1
      col -= 1
    elif row > 0 and distance[row][col] == distance[row - 1][col] + 1:
      script.append(Edit("delete", source[row - 1], None))
      row -= 1
    else:
      script.append(Edit("insert", None, target[col - 1]))
      col -= 1

  script.reverse()
  return script

Compare this against LCS line by line. Both index subproblems by prefix pairs; both branch on whether the last characters match; both fill an $(m+1)\times (n+1)$ table where each entry reads its left, upper, and upper-left neighbors; both run in $\Theta (mn)$. The only differences are the costs and the optimization direction: LCS maximizes matched characters, edit distance minimizes edits. Sequence DPs are a single template, parameterized by what a match earns and a mismatch costs. Recognize the template and a whole family of problems (LCS, edit distance, sequence alignment, longest common substring, and string matching) falls to the same code.

Alignment, bioinformatics, and the quadratic wall

The LCS/edit-distance template is the single most consequential dynamic program in applied computing, because it is sequence alignment. Needleman and Wunsch (1970) introduced the $\Theta (mn)$ global-alignment DP for comparing protein and nucleotide sequences; Smith and Waterman (1981) adapted it to local alignment (the best-matching substring pair, by clamping the score at $0$ and tracking the global maximum, the same move the maximum-subarray DP makes). These two recurrences are the foundation of computational biology, and the diff utility, git's merge machinery, spell checkers, and DNA read-mapping all descend from the same table. Gotoh (1982) refined the model with affine gap penalties — charging a large cost to open a gap and a small cost to extend it, which needs three coupled tables but stays $\Theta (mn)$ — because a single long insertion is biologically more plausible than many scattered ones.

The catch is scale. A $\Theta (mn)$ table is fine for two short strings but ruinous for two human chromosomes, and the Hirschberg linear-space trick (noted above) fixes the memory but not the time. Whether the time can be beaten is now settled conditionally: Backurs and Indyk (2015) and Bringmann and Künnemann (2015) proved that edit distance and LCS admit no strongly subquadratic $O(n^{2-\epsilon })$ algorithm unless the Strong Exponential Time Hypothesis is false. So the quadratic table is a genuine wall, and the practical response has been to give up exactness: heuristic aligners like BLAST (Altschul et al., 1990) and FASTA seed on short exact matches and extend them, trading a guarantee of optimality for the speed that made genome-scale search possible. The abstract define the subproblem, fill the table discipline of this lesson is, in this one instance, a multi-billion-dollar tool.⁵

Takeaways

• Index sequence subproblems by prefixes: $\mathrm{OPT}(i,j)=LCS-length(A[\mathrm{1..}i],B[\mathrm{1..}j])$ is the key to LCS, after the Step 0 move of solving for length first.
• The recurrence is a $\max$ over three cases (drop $A[i]$ in case 1, drop $B[j]$ in case 2, or extend the diagonal by $1$ when $A[i]=B[j]$ in case 3) over a base case of $0$ for an empty prefix.
• Prove it by induction on $i+j$ in two directions: $\ge$ (build a witness subsequence) and $\le$ (every common subsequence fits one of the three cases).
• Fill the $(m+1)\times (n+1)$ table in $\Theta (mn)$; reconstruct in a second pass, walking backwards from $\mathrm{OPT}(m,n)$ and emitting a character on every diagonal match.
• Only the length is needed? Two rows give $\Theta (\min (m,n))$ space, at the cost of losing the reconstruction.
• Edit distance is the same dynamic program: same prefix subproblems, same table shape, same $\Theta (mn)$, minimizing edits instead of maximizing matches. Sequence DP is one reusable template.