DP on DAGs
Every DP You've Ever Written Is a DAG
That's not a metaphor. Every DP recurrence defines a DAG of state dependencies. When you write dp[i] = max(dp[i-1], dp[i-2] + val[i]), states i-1 and i-2 point to state i. Process them in topological order -- which for linear DP is just left to right.
The power of explicit DAGs is that the dependency structure isn't always a neat line or grid. Topological sort handles any shape of dependencies.
Longest Path in a DAG
Longest path in a general graph is NP-hard. In a DAG, it's O(V + E).
Algorithm:
- Compute a topological order.
- Initialize
dp[source] = 0, everything else = negative infinity. - Process nodes in topo order. For each outgoing edge u → v with weight w:
dp[v] = max(dp[v], dp[u] + w).
// topo = topological order from Kahn's
fill(dp, dp + n + 1, -1e18);
dp[1] = 0;
memset(par, -1, sizeof(par));
for (int u : topo) {
if (dp[u] < -1e17) continue; // unreachable
for (auto [v, w] : adj[u]) {
if (dp[u] + w > dp[v]) {
dp[v] = dp[u] + w;
par[v] = u;
}
}
}
The par[] array tracks which predecessor gave the best value, enabling path reconstruction.
💡 Key insight. Topo order guarantees that when you process node v, all predecessors of v have already been processed. So
dp[v]gets the correct maximum.
Longest Path Trace
DAG (unweighted, so all edges have weight 1):
Topo order: [1, 2, 3, 4, 5]
| Process | Node | Outgoing Edges | Updates | dp[] | par[] |
|---|---|---|---|---|---|
| init | -- | -- | dp[1]=0 | [0, -inf, -inf, -inf, -inf] | [-1,-1,-1,-1,-1] |
| 1 | 1 | 1→2, 1→3 | dp[2]=1, dp[3]=1 | [0, 1, 1, -inf, -inf] | [-1, 1, 1, -1, -1] |
| 2 | 2 | 2→4 | dp[4]=2 | [0, 1, 1, 2, -inf] | [-1, 1, 1, 2, -1] |
| 3 | 3 | 3→4, 3→5 | dp[4]=max(2,2)=2, dp[5]=2 | [0, 1, 1, 2, 2] | [-1, 1, 1, 2, 3] |
| 4 | 4 | 4→5 | dp[5]=max(2,3)=3 | [0, 1, 1, 2, 3] | [-1, 1, 1, 2, 4] |
| 5 | 5 | -- | -- | [0, 1, 1, 2, 3] | [-1, 1, 1, 2, 4] |
Longest path to node 5: 3 edges.
Reconstruct: par[5]=4, par[4]=2, par[2]=1. Path: 1 → 2 → 4 → 5.
CSES Longest Flight Route
Problem: N cities, M one-way flights. Find the longest route from city 1 to city N (most flights taken). Print the route, or "IMPOSSIBLE."
This is exactly longest path in a DAG from 1 to N.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> adj[n + 1];
int indeg[n + 1] = {};
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
indeg[v]++;
}
// Kahn's
queue<int> q;
for (int i = 1; i <= n; i++)
if (indeg[i] == 0) q.push(i);
vector<int> topo;
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (int v : adj[u])
if (--indeg[v] == 0) q.push(v);
}
// DP
vector<long long> dp(n + 1, -1e18);
vector<int> par(n + 1, -1);
dp[1] = 0;
for (int u : topo) {
if (dp[u] < -1e17) continue;
for (int v : adj[u]) {
if (dp[u] + 1 > dp[v]) {
dp[v] = dp[u] + 1;
par[v] = u;
}
}
}
if (dp[n] < -1e17) {
cout << "IMPOSSIBLE" << endl;
return 0;
}
vector<int> path;
for (int v = n; v != -1; v = par[v])
path.push_back(v);
reverse(path.begin(), path.end());
cout << path.size() << "\n";
for (int v : path) cout << v << " ";
cout << endl;
}
⚠ Gotcha. Initialize dp values to negative infinity, not 0. If you use 0, unreachable nodes look like they have path length 0, and you might propagate from them incorrectly.
Counting Paths in a DAG
Same structure, different recurrence. Instead of max, use sum.
cnt[v] = sum of cnt[u] for all edges u → v. Base: cnt[source] = 1.
const int MOD = 1e9 + 7;
long long cnt[200005] = {};
cnt[1] = 1;
for (int u : topo) {
for (int v : adj[u]) {
cnt[v] = (cnt[v] + cnt[u]) % MOD;
}
}
Counting Paths Trace
Same DAG as before:
| Process | Node | Updates | cnt[] |
|---|---|---|---|
| init | -- | cnt[1]=1 | [1, 0, 0, 0, 0] |
| 1 | 1 | cnt[2]+=1, cnt[3]+=1 | [1, 1, 1, 0, 0] |
| 2 | 2 | cnt[4]+=1 | [1, 1, 1, 1, 0] |
| 3 | 3 | cnt[4]+=1, cnt[5]+=1 | [1, 1, 1, 2, 1] |
| 4 | 4 | cnt[5]+=2 | [1, 1, 1, 2, 3] |
| 5 | 5 | -- | [1, 1, 1, 2, 3] |
Paths from 1 to 5: 3. They are: 1→2→4→5, 1→3→4→5, 1→3→5.
CSES Game Routes
Problem: N cities, M one-way flights. Count paths from 1 to N, modulo 10^9 + 7.
Direct application of counting paths on a DAG:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
int n, m;
cin >> n >> m;
vector<int> adj[n + 1];
int indeg[n + 1] = {};
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
indeg[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++)
if (indeg[i] == 0) q.push(i);
vector<int> topo;
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (int v : adj[u])
if (--indeg[v] == 0) q.push(v);
}
vector<long long> cnt(n + 1, 0);
cnt[1] = 1;
for (int u : topo) {
for (int v : adj[u]) {
cnt[v] = (cnt[v] + cnt[u]) % MOD;
}
}
cout << cnt[n] << endl;
}
Shortest Path in a DAG
Same template, replace max with min:
fill(dp, dp + n + 1, 1e18);
dp[1] = 0;
for (int u : topo) {
if (dp[u] > 1e17) continue;
for (auto [v, w] : adj[u]) {
dp[v] = min(dp[v], dp[u] + w);
}
}
This handles negative weights too -- something Dijkstra cannot do. For DAGs, topo-sort-based shortest path is strictly more powerful than Dijkstra and runs in O(V + E), no log factor.
💡 Key insight. On a DAG, shortest path, longest path, and path counting all use the same skeleton: topo sort + one pass. Only the recurrence changes (min, max, or sum). This is O(V + E) for all three.
The Connection Between DP and DAGs
Every DP problem defines a DAG implicitly:
- Nodes = DP states
- Edges = transitions between states
- Topo order = the order you fill the DP table
For knapsack, states are (item, capacity) pairs. For LIS, states are array indices. For edit distance, states are (i, j) positions. In every case, you process states in an order where dependencies come first.
When the dependency graph is explicit (like a flight network), you use Kahn's or DFS topo sort to find the order. When it's implicit (like knapsack), the loop structure encodes the order.
LC 329 -- Longest Increasing Path in a Matrix
Each cell is a node. Edge from cell (r1,c1) to (r2,c2) if they're adjacent and matrix[r1][c1] < matrix[r2][c2]. The "strictly increasing" condition guarantees no cycles -- it's a DAG.
You can solve this with memoized DFS (which implicitly does topo sort via recursion):
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int memo[201][201];
int dfs(vector<vector<int>>& mat, int r, int c) {
if (memo[r][c]) return memo[r][c];
memo[r][c] = 1;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < (int)mat.size() &&
nc >= 0 && nc < (int)mat[0].size() &&
mat[nr][nc] > mat[r][c]) {
memo[r][c] = max(memo[r][c], 1 + dfs(mat, nr, nc));
}
}
return memo[r][c];
}
The memoized DFS naturally processes nodes in reverse topo order. No explicit topo sort needed.
⚠ Gotcha. You can also solve this by sorting all cells by value and processing smallest first. That's an explicit topo order based on the fact that edges only go from smaller to larger values.
Try It
The starter code sets up longest path from 1 to N. Fill in the Kahn's, DP, and path reconstruction sections.
Test case 1:
Test case 2 -- no path:
Challenge: Modify the code to count the number of longest paths (not just any paths, but paths of maximum length). Hint: track both dp[v] and cnt[v], updating cnt only when dp improves or ties.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES Longest Flight Route | cses.fi/problemset/task/1680 | Medium |
| CSES Game Routes | cses.fi/problemset/task/1681 | Medium |
| LC 329 — Longest Increasing Path in a Matrix | leetcode.com/problems/longest-increasing-path-in-a-matrix | Hard |