Understanding the linear DP pattern

A large family of problems asks us to compute an answer over a sequence, scanning it one position at a time, where the answer at each position is built directly from the answers at a small number of nearby positions. Counting the ways to climb a staircase, finding the cheapest way to reach the end of a path, or deciding whether a position can be reached at all are all problems of this kind. We move along the sequence, and at every step the answer we want depends only on a handful of steps we have already solved.

Problems like these are solved by the linear DP technique, where we lay out one subproblem per position of the sequence and fill them in order, each from its neighbours. Because the work flows straight along the sequence, the technique is simple, fast, and the natural first dynamic programming pattern to learn.

The linear DP pattern is a classification of problems that can be solved using the linear 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 subproblems of linear DP form a 1D array dp[0..n-1]

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

The linear DP technique

Every linear 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.