Graph Theory37 sections · 1633 units
Open in Course

When to Use DP on DAGs

Problem recognition

Use DP on DAGs when:

1.1. The graph is a DAG (explicitly or implicitly)

2.2. you are optimizing or counting over paths

3.3. Each subproblem depends only on earlier subproblems Examples: shortest path, longest path, counting paths, maximum weight path, minimum cost path. If the graph has cycles, you need a different approach. If the problem asks for connectivity or reachability, DFS/BFS might be better.