Dynamic Programming21 sections · 916 units
Open in Course

Pattern - String DP

Recognition tips

How do you recognize a string DP problem?

1.1. Comparing two strings? Probably 2D (two-dimensional) DP with dp[i][j]dp[i][j].

2.2. Looking for common structure? Think LCS pattern (match/skip).

3.3. Converting one string to another? Think Edit Distance pattern (multiple operations).

4.4. Counting ways? Same structure, but sum instead of max/min. The formula always asks: what happens at position (i,j)(i, j) based on whether characters match?