Understanding the dual-sequence DP pattern

A large family of problems has two sequences and asks a single question about the pair, like, how similar they are, how cheaply one can be turned into the other, or how much of one appears inside the other. Finding the longest subsequence two strings share, counting the fewest edits that rewrite one word into another, or checking whether a string can be built by interleaving two others are all problems of this kind. The answer is never about one sequence alone, it is about how the two line up against each other.

Problems like these are solved by the dual-sequence DP technique, where we lay out one subproblem per pair of positions, one position in each sequence, and build each pair from slightly smaller pairs. Because the two sequences are walked together, the subproblems fit naturally into a two-dimensional table, and the technique is the standard way to align, compare, or transform a pair of sequences.

The dual-sequence DP pattern is a classification of problems that can be solved using the dual-sequence DP technique.

Note that each of the two sequences can be an array or a string, anything indexed by a position 0, 1, ..., n-1. From here on we will call them sequences s1 of length m and s2 of length n.

The states of dual-sequence DP form a 2D table dp[i][j]

In this lesson we will learn the dual-sequence DP technique, why it qualifies as a dynamic programming problem, and how to solve it both top-down and bottom-up.

The dual-sequence DP technique

Every dual-sequence DP problem is an instantiation of the Bellman optimality equation, and to write that equation we first fix its main components, the action set, the cost function, and the transition function. Everything else, the recurrence, the dependency order, and the target state, follows from them.