Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are
- prefix/postfix of a string/sequence/array
- both prefixes/postfixes of a pair of strings/sequences/arrays
- an interval of a string/sequence/array
- a rooted subtree
What are the other types of subproblems (and examples/references) for dynamic programming?
Tables are sometimes used. Dynamic programming over trees (for example: maximum independent set) doesn't normally use a table [=array] to memoize the recurrence; it uses a tree, or in some cases a tree of arrays, or an array of trees, or in some cases a Cartesian product of trees. Similarly for dynamic programming over dags or dynamic programming over tree decompositions for graphs of bounded treewidth.
I would like to know dynamic programming examples over, e.g., a tree of arrays, an array of trees, a Cartesian product of trees, tree decompositions, or more general graphs.