Dynamic Programming • Pattern

DP on Strings

String matching problems often rely on comparing two strings recursively. We use a 2D grid to track the relationships.

Overview

LCS (Longest Common Subsequence) is the mother of all string DP problems. Edit Distance, Distinct Subsequences, etc. are derived from this pattern.

The state `dp[i][j]` always refers to the relationship between the prefix `s1[0..i-1]` and `s2[0..j-1]`.

If the characters match, we typically extend the sequence: `dp[i][j] = 1 + dp[i-1][j-1]`.

If they don't match, we branch out and find the optimal combination by ignoring the current char from `s1` or `s2`.

S1 \ S2	""	a	c
""	0	0	0
a	0	0	0
b	0	0	0
c	0	0	0

Code Tracker

:::

1for (let i = 1; i <= m; i++) {

2 for (let j = 1; j <= n; j++) {

3 if (s1[i-1] === s2[j-1]) {

4 dp[i][j] = 1 + dp[i-1][j-1];

5 } else {

6 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

7 }

8 }

9}