Top-down order of execution

The recurrence is a mathematical statement: "the value at s is some combination of the values at the smaller states that s depends on". The top-down implementation is the same statement, transcribed into code: a function dp(s) whose body says "compute the value at s by asking dp for each of the smaller states it depends on and combining the answers". Top-down execution is the most direct realisation of the recurrence relation with the addition of a cache, which sits between the function and its own self-calls so that each state's value is computed exactly once across the whole computation.

The recurrence, transcribed line for line into a function.

In this lesson we look at the generic function template for top-down order of execution, how the cache sits inside it, how the dependency order emerges implicitly from the recursion, the strengths and weaknesses of the approach, and the practical implementation patterns. 

Components of top-down execution

The function

The recursive function for the top-down execution of the dynamic programming problem follows a fixed template, regardless of the problem it is solving. Given below are the five lines that make up the template for every top-down dynamic programming function.

  1. 1The first line names the function and declares that it takes a state, and only a state as its argument.
  2. 2The second is the cache check, the line that turns a brute-force exponential recursion into a polynomial-time dynamic programming: it ensures that any state's value is computed at most once across the entire computation, no matter how many recursive calls would otherwise have re-derived it.
  3. 3The third is the base-case anchor: without it, the recursion has no terminating condition.
  4. 4The fourth is the recursion*: for each action a from A(s) available at a state s, compute T(s, a), recurse on it, combine with the immediate contribution c(s, a), and aggregate across actions via opt.
  5. 5The fifth stores the computed value in the cache and returns it. Without the storage, the cache would never grow and every call would do the full work from scratch.

The template for every top-down dynamic programming function.

Liking the course? Check our discounted plans to continue learning.

Subscribe