Identifying the subsequence DP pattern
The subsequence DP pattern solves problems where the input is a single sequence and the answer is the best subsequence we can pick from it, where what counts as best is defined by the problem. These are generally medium problems where the state stays a single ending index, but each state looks back at every earlier position, which gives the pattern a quadratic O(N^2) running time, where N is the length of the sequence.
When a problem statement, or its natural recursive solution, fits the template below, it is a subsequence DP problem.
Given a sequence of length
n, for all 0 <= i < n compute dp(i), the optimum over all subsequences where the last chosen element is at index i, built from the earlier states j where j < i and the constraint f(j, i) holds true, combining them with the operator pair (opt and ⊕). The answer is the best (opt) of dp(0), dp(1), ..., dp(n-1).How to identify the subsequence DP pattern
There are three signals that tell us a problem fits the subsequence DP pattern.
Pairwise relationship between elements of valid subsequence
If the input is a single array or string, and the goal is one number about the best subsequence inside it, it is generally a subsequence DP pattern problem.
A subsequence keeps the original order from the input but may skip any elements it likes, and the rule that constrains the pick is pairwise, i.e. each kept element must relate to the element kept just before it via some constraint function f. For example the next element may be strictly larger than, divisible by, or alternating in direction from the previous element. Words like subsequence, increasing, chain, or each next element point to this signal.
Liking the course? Check our discounted plans to continue learning.