The DP on DAGs Pattern

Finding the longest path in a general graph is NP-hard.

But in a DAG, it is easy with DP. Idea: Process nodes in topological order. For each node $v$, dp[v] stores the longest path ending at $v$. For each edge $u \to v$, update dp[v] = max(dp[v], dp[u] + 1). Start with dp[source] = 0, all others at $-\infty$. Answer is dp[destination]. Shortest path works the same way, use $\min$ instead of $\max$.