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 . Initialize dp[source] = 1 and dp[u] = 0 for all other nodes.
For each node in topological order, for each outgoing edge , update: dp[v] += dp[u] After processing all nodes, dp[destination] is the total count. This works because each path to through is counted exactly once.