The mental model for dynamic programming

We learnt about the formal definition of when a dynamic programming solution applies to a problem in the previous lesson. If a problem has both optimal substructure and overlapping subproblems, it tells us whether dynamic programming is the right tool for a given problem, but it does not tell us how to actually design a dynamic programming solution once we have decided to use one.

The bridge between the two is a single mental model that applies to every dynamic programming problem. Every dynamic programming problem can be pictured as the same kind of structure: a graph of subproblems, with edges for dependencies. Once we see the structure clearly, designing a dynamic programming algorithm for any specific problem reduces to asking a small set of natural questions about it. Each question pins down one piece of the algorithm, and there are four pieces: the state, the recurrence, the base cases, and the order of execution that form the pillars of any dynamic programming algorithm.

In this lesson we will learn a mental model that applies to every dynamic programming problem and is critical for designing an dynamic programming algorithm for such problems.

The recursion tree of a dynamic programming problem is a DAG

Every dynamic programming algorithm is, at heart, a refinement of recursion. We cannot have a dynamic programming solution without first having a recursive one, explicit or implicit, and the recursion tree of any dynamic programming problem has a handful of features that are universal across problems.

The root node of the recursion tree is the original problem. Whatever we ultimately want to compute lives at the top.