Core pattern
Two Sequence / String DP
Step 7 of 14Pattern 5 of 7
×How to recognize it fast
If two strings or sequences appear together in the same question, the safest first thought is usually 2D prefix DP.
When you see
two stringscompare sequencescommon subsequenceedit operationsdelete to make equal
Think
- Let dp[i][j] represent an answer on prefixes of both sequences.
- If characters match, I usually use the diagonal. If not, I borrow from neighbors.
What to do once the pattern is clear
Core trick
- Define dp[i][j] using the first i characters of one string and first j of the other.
- When characters match, the diagonal transition is usually the key move.
- When they do not match, compare top and left style transitions based on the question.
Shortcut recognition
Two strings in the same problem statementMatch / skip / edit decisionsCommon subsequence or delete operations
Hidden trick
Do not jump straight to optimization. Most bugs disappear once the 2D meaning of dp[i][j] is written cleanly on paper first.
LCS core idea
if (a[i - 1] === b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1]; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])