Two-Dimensional Dynamic Programming: Longest Common Subsequence and Edit Distance

01The Invariant of Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) problem finds the length of the longest subsequence present in both strings text1 and text2 in the same relative order (not necessarily contiguous). LCS is the mathematical foundation of git diff, biological DNA alignment (BLAST), and plagiarism detection systems.

Let dp[i][j] represent the length of the LCS of text1[0..i-1] and text2[0..j-1]. We establish the fundamental recurrence relation:

1. If text1[i-1] == text2[j-1]: The characters match! They extend the LCS of the prefixes: dp[i][j] = 1 + dp[i-1][j-1].

2. If text1[i-1] != text2[j-1]: The characters do not match. The best subsequence comes from either skipping text1's character or text2's character: dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]).

02LCS 2D Table Trace

Tracing text1 = 'ABCDE' and text2 = 'ACE' across the 2D DP matrix illustrates how matches propagate diagonally while mismatches inherit from top and left neighbors:

+---+---+---+---+---+|   | ø | A | C | E |+---+---+---+---+---+| ø | 0 | 0 | 0 | 0 || A | 0 | 1 | 1 | 1 | (Match 'A': 1 + dp[0][0])| B | 0 | 1 | 1 | 1 | (Mismatch: max(dp[1][j], dp[2][j-1]))| C | 0 | 1 | 2 | 2 | (Match 'C': 1 + dp[2][1])| D | 0 | 1 | 2 | 2 | (Mismatch: max(dp[3][j], dp[4][j-1]))| E | 0 | 1 | 2 | 3 | (Match 'E': 1 + dp[4][2] = 3)+---+---+---+---+---+Result: LCS length = 3 ('ACE')

03Levenshtein Edit Distance: Insert, Delete, Replace

Edit Distance measures the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform word1 into word2. It powers spell checkers, autocomplete suggestions, and speech recognition correction.

Let dp[i][j] be the edit distance between word1[0..i-1] and word2[0..j-1]:

1. Base cases: dp[i][0] = i (delete all i characters), dp[0][j] = j (insert all j characters).

2. If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (no cost).

3. If characters differ, take the minimum of three operations plus 1 cost: dp[i][j] = 1 + min(dp[i-1][j] (Delete), dp[i][j-1] (Insert), dp[i-1][j-1] (Replace)).

04Space Optimization: Rolling Arrays

In production services matching long DNA sequences or comparing 50,000-line source code files, allocating an (m x n) integer matrix requires hundreds of megabytes of heap memory, triggering GC pressure.

Observing the state transitions reveals that computing dp[i][j] depends ONLY on the current row (dp[i]) and the previous row (dp[i-1]). Elements from two rows prior are never accessed again.

By replacing the full 2D matrix with two 1D arrays of size min(m, n) (prevRow and currRow), memory complexity drops from quadratic O(m * n) to linear O(min(m, n)), while preserving O(m * n) runtime.

05Production Architecture & Engineering Trade-Offs

Dynamic programming solves complex optimization problems by decomposing them into overlapping subproblems and enforcing optimal substructure. However, inexperienced engineers frequently struggle with state-space explosion: defining state dimensions that require excessive memory or state transitions that duplicate computations.

In production applications—such as continuous resource scheduling, query optimization in database planners, and automated financial portfolio rebalancing—space optimization is critical. By recognizing that state transitions often depend only on the immediate previous time step or row, engineers routinely optimize memory consumption from quadratic O(m * n) down to linear O(n) using rolling buffers.