DP fundamentals: states and transitions · 3 of 3
DP on DAGs
Fill a DP table over a directed acyclic graph in topological order, and rebuild the best route from parent links.
Books1
Links3
- Algorithms, Chapter 6: Depth-first search Section 6.4 shows that a memoized recursion is a depth-first search of the dependency graph, and that a loop fills the same values in topological order, then finds the longest path in a DAG. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)
- Topological Sort Its Dynamic Programming section solves Longest Flight Route in topological order, and its problem list includes Game Routes. usaco.guide (opens in a new tab)
- Topological Sorting Builds a topological order with depth-first search, the other standard way to get an evaluation order. cp-algorithms.com (opens in a new tab)