templates · Dynamic programming

Two-string DP (LCS, edit distance)

  • Two strings (or two arrays) and a question about matching them up
  • "Longest common subsequence", "fewest edits", "how many ways does t appear in s"
  • Each step looks at the last letter of both prefixes: match it, or drop one

2D DP on two strings (LCS / edit distance)

the one rule

The invariant

dp[i][j] is the final answer for the prefixes a[0..i) and b[0..j), and row 0 / column 0 mean an empty prefix.

write it from memory

The template

longest common subsequence

javajava.util.*
/** Longest Common Subsequence of a and b. */static int lcs(String a, String b) {    int m = a.length(), n = b.length();    int[][] dp = new int[m + 1][n + 1];                  // dp[i][j] = answer for a[0..i) and b[0..j)    // row 0 and column 0 stay 0: an empty prefix has nothing in common    for (int i = 1; i <= m; i++) {        for (int j = 1; j <= n; j++) {            if (a.charAt(i - 1) == b.charAt(j - 1)) {    // last letters match                dp[i][j] = dp[i - 1][j - 1] + 1;         // use both letters            } else {                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // drop a letter from one side            }        }    }    return dp[m][n];                                     // both full strings}

The extra row and column for the empty prefix remove every "is i - 1 valid?" check. Bas itna yaad rakho: dp index i means letter i - 1.

fill in the blanks — only these lines change per problem

  1. line 4What a cell means for two prefixes: common length, edits needed, number of ways, or true/false.
  2. line 5Row 0 and column 0: 0 for LCS, the length for edit distance, 1 for "ways" when the pattern is empty.
  3. line 8What counts as a match: equal letters, or a wildcard like ? / ..
  4. line 9The value when the last letters match: diagonal + 1, just the diagonal, or diagonal + the cell that skips a letter of s (the string you pick letters from), for counting (Distinct Subsequences).
  5. line 11The value when they do not: max of top and left for LCS, 1 + min of three for edit distance.

edit distance

javajava.util.*
/** Edit Distance: fewest inserts, deletes and replaces that turn a into b. */static int editDistance(String a, String b) {    int m = a.length(), n = b.length();    int[][] dp = new int[m + 1][n + 1];                  // dp[i][j] = edits to turn a[0..i) into b[0..j)    for (int i = 0; i <= m; i++) dp[i][0] = i;           // delete all i letters    for (int j = 0; j <= n; j++) dp[0][j] = j;           // insert all j letters    for (int i = 1; i <= m; i++) {        for (int j = 1; j <= n; j++) {            if (a.charAt(i - 1) == b.charAt(j - 1)) {                dp[i][j] = dp[i - 1][j - 1];             // same letter: no edit            } else {                int replace = dp[i - 1][j - 1];                int delete = dp[i - 1][j];                int insert = dp[i][j - 1];                dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));            }        }    }    return dp[m][n];}

Same table, different base case: turning a prefix into an empty string costs its length.

complexity

What it costs

time O(m × n)
One cell per pair of prefix lengths, and each cell reads three neighbours in O(1).
space O(m × n), or O(n)
The full table. Each row only reads the row above, so two rows are enough if memory matters.

watch out

Common bugs

  • Reading a.charAt(i) instead of a.charAt(i - 1). With the empty row, cell i is letter i - 1.
  • Sizing the table m × n instead of (m + 1) × (n + 1), so the full strings have no cell.
  • Mixing up subsequence (letters may be skipped) with substring (must be contiguous: reset to 0 on a mismatch).

use it

Practise it on

learn it properly