Discovering the state

In the previous lesson we developed the formal definition of a state, its two complementary views and the three criteria a correct state must satisfy. Knowing what a state is, however, is a very different skill from being able to find one for a new problem. Discovering the state is the hardest creative step when solving any dynamic programming problem.

In this lesson we lear a step by step process to discover a state for any dynamic programming problem and checks to ensure the state is correct. It gives a reliable starting point that works on almost every of dynamic programming problems we will ever encounter.

Step 1: Write the brute-force recursion

The first step is not even think about dynamic programming and write the natural brute-force recursive solution that solves the problem by exploring every possibility. At this state, efficiency is not a concern and the only goal is to make sure the solution is correct. We work towards producing a function that would produce the right answer for any input.

The reason we start with a brute force recursive solution is that it makes every decision explicit. At each recursive call, the function picks an action from a set of legal actions, recurses on the smaller subproblem that results from that action, and combines the answers from those recursive calls. It establishes a known-correct algorithm that we trust, and the candidate state is then read off that recursion and refined later.