Lessons from Game Routes

This problem shows how DP on DAGs extends beyond finding the longest path. Instead of maximizing, we count all paths. The core insight is that counting paths follows the same topological order pattern, but uses addition instead of max.

The state ways[v] counts paths from source to $v$. The transition sums contributions from all predecessors: ways[v] = Σ ways[u] for all edges $u \to v$. This works because each path through $u$ extends uniquely to $v$.

You've now seen two DP patterns on DAGs: longest path (Longest Flight Route) and counting paths (Game Routes). The template is always the same: topological order plus DP transitions. The only difference is the operation (max vs sum).