Two Strings, One Table

You can define states. You can write recurrences. You can handle base cases.

But what happens when the DP table has TWO dimensions — one for each string? And the transition depends on whether characters MATCH?

You are about to build that table from scratch and discover the rule yourself.

String Surgery

Build the LCS grid cell by cell. Trace the backtrack path. Then challenge the assumption that string DP always needs a 2D table.

1 / 18

Compare A (row) vs B (col) at cell (1,1)

""
B
D
C
B
""
0
0
0
0
0
A
0
?
?
?
?
B
0
?
?
?
?
C
0
?
?
?
?
B
0
?
?
?
?

Characters don't match. Where does the cell value come from?

The Diagonal Rule

The recurrence you discovered — diagonal + 1 for match, max(up, left) for mismatch — is not specific to LCS.

Edit distance uses the SAME grid structure: diagonal means “characters match, no edit needed.” Up means “delete from s1.” Left means “insert into s2.” The grid shape is shared; only the TRANSITION meaning changes.

And not every string problem needs that grid. Word Break only needs 1D. Palindrome partitioning uses n * n on a single string. The state shape follows from the PROBLEM definition, not from “it's about strings.”