Part VI · Graph Algorithms and Tree-Graph Techniques
37. Graph Dynamic Programming and DAG Applications
5 lessons•20 topics•Intermediate / Advanced
5 of 5 lessons published
37.015 animated
DAG DP patterns
- Topological state order
- Number of paths
- Maximum path weight
- Minimum cost path
- Reachability counts
37.024 animated
Multi-state graph DP
- Color-count paths
- Paths with limited stops
- Edge count constraints
- Resource-constrained paths
37.032 animated
Longest paths
- Longest path in DAG
- Why general longest simple path is hard
- Reconstructing path
37.044 animated
Graph games
- Winning/losing states on DAG
- Retrograde analysis
- Terminal states
- Minimax on DAG
37.054 animated
Functional graph DP
- Successor links
- Cycles with in-trees
- Jump pointers
- Path length to cycle