DP on DAGs
Shortest/longest path in DAGs, counting paths, and DP with topological order.
Lessons
1. Intro
The Goal
2. Why DAGs Are Special
No cycles = DP works
3. Topological Order Refresher
Linear ordering of nodes
4. The DP on DAGs Pattern
Process in topological order
5. Quiz: Topological Order
Knowledge check
6. Shortest Path in DAGs
Better than Dijkstra
7. Defining the DP State
What dp[u] means
8. Shortest Path Algorithm
Step by step process
9. Shortest Path Example
Walking through an instance
10. Longest Path in DAGs
Flip the minimization
11. When You Need Longest Paths
Scheduling and critical paths
12. Quiz: Path Types
Knowledge check
13. Problem - Longest Flight Route
CSES 1680
14. Core idea - Counting Nodes
Edge weights are 1
15. Checking for Cycles
Networks can have cycles
16. State Definition
dp[u] = max cities to u
17. Reconstructing the Route
Backtracking from destination
18. Longest Flight Route - Implementation
Complete solution
19. Edge Case - Unreachable Destination
Handling IMPOSSIBLE
20. Walkthrough Example
Step by step trace
21. Lessons Learned
summary
22. Counting Paths
How many ways to reach
23. Problem - Game Routes
CSES 1681
24. DP State for Counting
dp[u] = number of paths to u
25. Why you Add Counts
Paths are independent
26. Handling Large Counts
Output modulo 10^9+7
27. Game Routes - Implementation
Complete solution
28. Walkthrough Example
Tracing the DP
29. Quiz: Counting Paths
Knowledge check
30. Common Mistake - Initialization
Base case matters
31. Common Mistake - Modulo Placement
Apply after every operation
32. Multiple Sources
Initialize multiple base cases
33. Multiple Destinations
Sum over all endpoints
34. Backward DP
Reverse edges for DP
35. Combining Two DPs
Paths through a node
36. Quiz: DP Details
Knowledge check
37. Problem - High Score
CSES 1673
38. Positive Cycles
Infinite score problem
39. Using Bellman-Ford
Negate for maximization
40. Cycles Must Be On Path
Reachable from 1 and reaches n
41. High Score - Implementation
Complete solution
42. When DAG DP Fails
Cycles break the pattern
43. DP on Trees
Trees are DAGs
44. Vocabulary - Relaxation
Updating distance estimates
45. Vocabulary - Topological Sort
Linear ordering of DAG nodes
46. Practice - Course Schedule II
LeetCode 210
47. Practice - Cheapest Flights
LeetCode 787 with constraint
48. When to Use DP on DAGs
Problem recognition
49. Implicit DAGs
State space graphs
50. Section Recap
What we learned