I think of dynamic programming as a bottom-up computation, but that view can be slightly misleading. For example, consider keeping track of the connected components of a forest F in a graph of bounded treewidth.
For a bag B, let G(subtree(B)) denote the subgraph induced by the nodes appearing in bag B (let's call those portal nodes) and in all of its descendant bags as well. Let G(B) denote the constant size graph induced by just the portals.
Consider the connected components of (F intersect G(subtree(B))). They induce a partition pi(B) of the portals.
- for a leaf bag, pi(B) = the connected components of (F intersect G(B))
- for a bag B with two children B1 and B2, pi(B) is obtained by "combining" pi(B1), pi(B2), and (F intersect G(B)).
It's a bottom-up recurrence.
Consider instead the connected component of F, the global forest. They also induce a partition sigma(B) of the portals.
- for the root bag, sigma(B)=pi(B)
- for a bag B with parent bag B', sigma(B) is obtained by "combining" sigma(B'), pi(B), and (F intersect G(B union B')).
It's a top-down recurrence.
Since all recurrence formulas are local, a dynamic program can do both computations at the same time, and thus a DP algorithm can be assumed, while it is working on a bag B, to have access to the partition of the portals in the global forest: working bottom up, it makes guesses that will be validated later at a higher level of the tree. Thus, one recurrence is of the form: compute, then memorize a summary of the computation done in G(subtree(B)). The other recurrence is of the form: guess a summary of the future computation, then verify. In the DP the two computations are intertwined.
Borradaile, Klein and myself are using something much like this in a paper on Euclidean Steiner forest. Bateni, Hajiaghayi and Marx are using essentially this in a paper on Steiner forest in planar graphs and graphs of bounded treewidth. Writing up the details of such dynamic programs is a bit messy, yet it is conceptually simple. I think that the difficulty in presentation comes from this mix of bottom-up and top-down.
Are there other examples of such dynamic programs? Are there models of good writing for that?