Course contentsShow
← Computer Science
Lesson 951 of 2,87222. Dynamic ProgrammingFree lesson

DP on DAGs: Counting Paths

Counting the number of paths between nodes in a DAG through memoized recursion.

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.