Understanding the interval DP pattern

A large family of problems asks us to combine a whole sequence by repeatedly joining its neighbouring pieces, where the cost of each join depends on where we cut. Multiplying a chain of matrices in the cheapest order or merging piles of stones at the least total cost are all problems of this kind. The items sit in a fixed sequence, we are free to choose the order in which neighbouring pieces are combined, and every choice of cut carries its own cost.

Problems like these are solved by the interval DP technique, where we lay out one subproblem per contiguous range of the sequence and build each range from the two smaller ranges it splits into. Because every answer rests on shorter ranges, we can solve the shortest ranges first and grow outward until the whole sequence is covered.

The interval DP pattern is a classification of problems that can be solved using the interval 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 interval DP table, the upper triangle with target dp(0, n-1)

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

The interval DP technique

Every interval 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 order of execution, and the target state, follows from them.