Two Sequence DP
State is a pair of prefixes. When the characters match, consume both; otherwise take the best of the branching options.
Dynamic ProgrammingO(n * m)New10 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
longest common subsequence
edit distance
wildcard matching
shortest common supersequence
The template
Get this into muscle memory, then adapt the condition per problem.
for (let i = 1; i <= n; i++)
for (let j = 1; j <= m; j++)
dp[i][j] = a[i-1] === b[j-1]
? dp[i-1][j-1] + 1
: Math.max(dp[i-1][j], dp[i][j-1]); Watch Longest Common SubsequenceIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Two strings means a two dimensional state of prefix lengths.
- 2Compare the last characters and branch on match or mismatch.
- 3Reconstruct the actual sequence by walking the table backwards.
Drill it
Every problem in the bank that uses this pattern.
0 / 10 solved