DP on DAGs: Counting Paths
What you'll learn: How to efficiently count all possible paths between two nodes in a Directed Acyclic Graph using dynamic programming.
The Core Idea
In the previous lesson, you found the longest path in a DAG. Now, instead of finding one optimal path, you want to count how many paths exist between two nodes. Since a DAG has no cycles, you won't count paths infinitely—but paths can still branch and merge, making naive counting exponential.
The key insight: memoization saves you from recounting the same subproblem. If you've already calculated how many paths exist from node u to the destination, you don't need to compute it again when reaching u from a different starting point.
How It Works
Think of it like counting routes in a one-way street network. From your current intersection, you can take several streets. Each street leads to another intersection that also has multiple routes to your destination. Instead of exploring every combination repeatedly, you remember: "From intersection B, there are 5 ways to reach my goal." When you arrive at B from different directions, you just reuse that count.
The recurrence relation:
- Base case:
count(destination) = 1(you've arrived) - Recursive case:
count(node) = sum of count(neighbor)for all outgoing neighbors
By processing nodes in topological order (or using memoized recursion), you ensure that when computing count(node), all its descendants are already computed.
Why Memoization Matters
Without memoization, counting paths becomes exponential—you'd recount the same downstream paths every time you reach a node via different routes. With memoization, each node's count is computed exactly once: O(V + E) time complexity.
Key Takeaway: Counting paths in a DAG is efficient with DP because memoization prevents redundant work—each node's path count to the destination is computed once and reused, turning an exponential problem into linear time.