Identifying the dual-sequence DP pattern
The dual-sequence DP pattern solves problems where the input is two sequences and finding the solution naively would need comparing an exponential number of alignments. These are generally medium problems where we compare the two sequences position by position, and at each pair of positions we make a local decision by looking at the two endpoint elements.
When a problem statement, or its natural recursive solution, fits the template below, it is a dual-sequence DP problem.
Given two sequences
s1 of length m and s2 of length n, for every pair of prefixes s1[0..i] and s2[0..j] we compute dp(i, j), the solution to the subproblem made from s1[0..i] and s2[0..j]. When the endpoints s1[i] and s2[j] match, dp(i, j) is built from the diagonal state dp(i-1, j-1), and when they differ it is built from the advance states dp(i-1, j) and dp(i, j-1), combined with the operator pair (opt and ⊕). The answer is dp(m-1, n-1).How to identify the dual-sequence DP pattern
There are two signals that tell us a problem fits the dual-sequence DP pattern.
There are two sequences and one answer
If the input is two sequences, and the goal is to compute a number, an optimum, a count, or a yes or no about how the pair compares, it is generally a dual-sequence DP pattern problem.
The answer is computed taking both the inputs in account rather than a single sequence alone, like a length they share, a cost to convert one into the other, or a verdict on whether one can be built from the other. A problem may mention a third string, like an interleaving target, but it is derived from the same two inputs.
Liking the course? Check our discounted plans to continue learning.