The order of execution

In the previous modules we built up three of the four pillars of a dynamic programming algorithm, namely the state that uniquely identifies subproblems, the recurrence relation that connects the and the base base cases that seed all the computed values. These pillars give us the specification of the algorithm that tells us what are the values of the state, but we still do not have a procedure that tells us how to obtain those values. To turn the specification into a running algorithm we need to decide in what order to evaluate the states and that is exactly what the order of execution tells us.

In this lesson, we will learn about the order of execution which is the fourth pillar of a dynamic programming algorithm. It is the one that takes us from the mathematical statement: "this is what dp(s) equals" to the operational statement: "this is how we obtain dp(s) on a real computer".

The dependency constraint

It is important to note that for any dynamic programming recurrence, whatever order we choose to evaluate the states, it must obey one rule: a state's value cannot be computed before the values of its dependencies are known. This is the single, non-negotiable constraint on any order of execution.

The rule is simply a restatement of the structure of the state space DAG. A directed edge from s to s' in the DAG means s depends on s'. The recurrence at s references dp(s'). To compute dp(s), we must already have dp(s') in hand as every state inherits a list of states that must be evaluated before it.