Definition of a state

In the previous module we built a mental model of a dynamic programming problem as a DAG of subproblems, and we narrowed down the process of designing a dynamic programming algorithm to answering four questions: what is each subproblem, how is it connected to other subproblems, where does the recursion bottom out, and in what order do we evaluate everything. Each of those four questions corresponds to one pillar of the dynamic programming framework.

The first question is the most important one by a wide margin and in this lesson we will learn in more detail how to answer it correctly. Before we can talk about how subproblems are connected, we have to be precise about what a single subproblem is, and we have to give it a name precise enough that two recursive calls referring to the same subproblem actually look identical to the algorithm. That naming scheme is the state, and getting it right is the entire creative challenge of dynamic programming. Once the state is correct, the rest of the algorithm easily falls into place. Conversely, if the state is wrong, every later step inherits that error and the algorithm will return wrong answers without any obvious bug to point at.

The formal definition

A state is a tuple s = (x1, x2, ..., xk), drawn from a set S called the state space, where each xi is a parameter and S is the set of all tuples that can ever arise during the computation. Each individual state corresponds to a single subproblem, and the value stored at that state written dp(s) or dp[s] is the solution to that subproblem.

A state is therefore three things at once, and it is worth holding all three in mind: