Request for examples to show various types of subproblems in dynamic programming

Question

Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are

1. prefix/postfix of a string/sequence/array
2. both prefixes/postfixes of a pair of strings/sequences/arrays
3. an interval of a string/sequence/array
4. a rooted subtree

What are the other types of subproblems (and examples/references) for dynamic programming?

---

Added: In a comment on this post, JeffE mentioned:

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.

Answer 1

Everything you need could be found on Topcoder.com (TCC for short).

Start with Dumitru's tutorial. Done that, you should be able to integrate the DP technique on various structures, like 2D grids, narrow ribbons, convex polygons, etc. to name just a few.

An archive of DP problem on TCC: https://www.topcoder.com/tc?module=ProblemArchive&sc=2&sd=desc&cat=Dynamic+Programming

And the match editorial is the best collection: https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=archive

I have learnt so much from these. Unfortunately, this editorial series stopped since 2008. From that time on, the SRMs are only discussed in the forum like these more recent SRMs: https://www.topcoder.com/blog/single-round-match-735-editorials/

A tagged search produces this: https://www.topcoder.com/blog/tag/srm-editorials/ So you may easily access all the recent SRMs.

SRM: Single Round Match (TCC is the arena of online competitive programming)

---

Please note that TCC has been gone through various reconstruction (since the integration with Data Science market). As a (unwanted) consequence, many links are broken but can be fixed by modifying some middle parts (as often the cases for decades-old websites)