Memoization and Dynamic Programming

Our topological sort algorithm is arguably the model for a wide class of dynamic programming algorithms. Recall that the dependency graph of a recurrence has a vertex for every recursive subproblem and an edge from one subproblem to another when we’re evaluating the first subproblem requires a recursive evaluation of the second. The dependency graph must be acyclic, or the naïve recursive algorithm would never halt.

Evaluating any recurrence with memoization is exactly the same as performing a depth-first search of the dependency graph. In particular, a vertex of the dependency graph is “marked” if the value of the corresponding subproblem has already been computed. The black-box subroutines $PreVisit$ and $PostVisit$ are proxies for the actual value computation.

Dynamic programming and reverse topological ordering

Carrying this analogy further, evaluating a recurrence using dynamic programming is the same as evaluating all subproblems in the dependency graph of the recurrence in reverse topological order—every subproblem is considered after the subproblems it depends on. Thus, every dynamic programming algorithm is equivalent to a postorder traversal of the dependency graph of its underlying recurrence.

$\underline{Memoize(x) :} \\ \hspace{0.4cm} if\space value[x]\space is\space undefined \\ \hspace{1cm} initialize \space value[x] \\ \hspace{1cm} for \space all \space subproblems \space y \space of \space x \\ \hspace{1.7cm} Memoize(y) \\ \hspace{1.7cm} update \space value[x] \space based \space on \space value[y] \\ \hspace{1cm} finalize\space value[x]$

$\underline{DFS(v) :} \\ \hspace{0.4cm} if \space v \space is\space unmarked \\ \hspace{1cm} mark \space v \\ \hspace{1cm} PreVisit( x ) \\ \hspace{1cm} for \space all\space edges\space v\rightarrow w \\ \hspace{1.7cm} DFS(w) \\ \hspace{1cm} PostVisit( x )$ ...