Counting Paths

Another common DP problem on DAGs is counting the number of distinct paths from a source to a destination. Define dp[u] as the number of paths from the source to node $u$. Initialize dp[source] = 1 and dp[u] = 0 for all other nodes.

For each node $u$ in topological order, for each outgoing edge $(u, v)$, update: dp[v] += dp[u] After processing all nodes, dp[destination] is the total count. This works because each path to $v$ through $u$ is counted exactly once.