Two-Dimensional State

In LIS (Longest Increasing Subsequence), you had one sequence and tracked "ending at position $i$". With two sequences A and B, you track progress in both. $dp[i][j]$ = some property of A[0..i-1] and B[0..j-1] The table has $(m+1) \times (n+1)$ cells where $m$ and $n$ are the string lengths.

Row 0 and column 0 represent empty prefixes. The formula for dp[i][j] depends on whether A[i-1] and B[j-1] match, and what you're trying to compute.