Understanding the subsequence DP pattern

A large family of problems asks us to pick the best subsequence out of a sequence, some of its elements kept in their original order, so that every kept element is compatible with the one kept before it. Finding the longest run of values that keeps increasing, the heaviest ascending pick of items, or the longest chain where each number divides the next are all problems of this kind. We are free to skip any element, so the chosen elements can sit far apart, and the element an answer extends can be anywhere to its left.

Problems like these are solved by the subsequence DP technique, where we compute for each position the best subsequence that ends exactly there, and build each of those answers by looking back over every earlier position that is allowed to come before it. This backward reach over the whole prefix is what sets the pattern apart, a subsequence decision is not limited to a neighbour or two, it may extend any compatible element anywhere earlier in the sequence.

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

Note that a sequence here can be an array or a string, anything indexed by a position 0, 1, ..., n-1. From here on we will use an array as our example, but everything applies to strings as well.

The states of subsequence DP form a 1D array dp[0..n-1]

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

The subsequence DP technique

Every subsequence DP problem is an instantiation of the Bellman optimality equation, built from a state together with its three components, the action set, the cost function, and the transition function. Everything else, the recurrence, the dependency order, and the target, follows from them.