DP on DAG

Quick Revisit

• USE WHEN: longest/shortest path in DAG, counting paths, dependency-aware optimization
• INVARIANT: process nodes in topological order so all predecessors are solved before the current node
• TIME: O(V + E) | SPACE: O(V)
• CLASSIC BUG: running DP without first verifying the graph is a DAG (cycles cause wrong answers)
• PRACTICE: ../12-practice-ladders/05-ladder-graphs.md

Process nodes in topological order so that every predecessor is already computed -- the universal technique for shortest paths, longest paths, and path counting on directed acyclic graphs.

Difficulty: [Intermediate]Prerequisites: Topological SortCF Rating: 1400-1700

---

Contents

• Intuition & Concept
• Visual Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• When to Reach for This
• Contest Cheat Sheet
• Common Mistakes
• Practice Problems
• Related Topics
• Further Reading
• Recap

---

Intuition & Concept

Suppose you have a directed graph with weighted edges and no cycles, and you want the longest path from node 1 to node $n$. Your first instinct might be Dijkstra -- but Dijkstra finds shortest paths, and negating edge weights to turn "longest" into "shortest" introduces negative edges, which break Dijkstra's greedy assumption. Bellman-Ford handles negative edges but runs in $O(nm)$, which is overkill. BFS only works on unweighted graphs.

The trick is embarrassingly simple once you see it: process the nodes in topological order.

When you visit node $v$ in topological order, every node $u$ with an edge $u\to v$ has already been visited and its DP value is final. So you can compute $dp[v]$ from the values of all its predecessors in a single pass. No relaxation loops, no priority queues -- just one sweep through the toposort.

This is the same principle behind every DP you have ever written. A DP recurrence works because you compute states in an order where all dependencies are resolved first. In a 1D DP like dp[i] = max(dp[j] + ...) for $j<i$, the "DAG" is implicit: state $i$ depends on earlier states $j$, and processing left-to-right is a topological order. DP on a DAG makes the graph explicit.

Graph → DP correspondence

Once you see one DP as a DAG, you can read every other DP through the same four labels:

Graph concept	DP concept
Node	A state of the subproblem
Edge $u\to v$ with cost $w$	A legal transition from one state to another, contributing $w$
Topological order	The order in which you compute states
Relaxation dp[v] = combine(dp[u] + w, dp[v])	The recurrence

When the chapter on DP starts naming "states" and "transitions," it is literally describing the nodes and edges of an implicit DAG. The table above is the dictionary.

Pull vs push: two equivalent viewpoints

The recurrence

$$dp[v]=\underset{(u,v)\in E}{max}(dp[u]+w(u,v))$$

is written pull-style: for each $v$, look at incoming edges and take the best predecessor. In code, that means iterating over a reverse adjacency list.

The implementations in this file use the push-style dual: for each $u$ in topological order, walk outgoing edges and update each neighbour $v$. The two are mathematically identical because every edge appears in both views, but the loops look different. Beginners get confused when the recurrence is written as a max over $u$ predecessors while the code iterates $v$ successors — that is just push vs pull, not a bug.

Pick whichever is convenient: pull is cleaner when you have a reverse graph or only know predecessors; push is cleaner when iterating outgoing edges is natural and the toposort is already in hand.

The recurrence for longest path from a source $s$:

$$dp[v]=\underset{(u,v)\in E}{max}(dp[u]+w(u,v))$$

Initialize $dp[s]=0$ and $dp[v]=-\mathrm{\infty }$ for all $v\ne s$. Process nodes in topological order. When you finish, $dp[t]$ is the longest path from $s$ to $t$ (or $-\mathrm{\infty }$ if $t$ is unreachable).

Swap max for min and you get shortest path in a DAG. Replace the recurrence with a sum and you get path counting. The skeleton is always the same: toposort, then sweep.

When this appears on Codeforces: any problem involving a DAG (or a graph you can turn into a DAG) where you need to optimize or count something along paths. Common tags: dp, graphs, shortest paths, dfs and similar. Typical rating: 1400-1700 for clean DAG problems, 1800+ when you need to construct the DAG from a non-obvious structure.

Common traps at the ~1100 level:

• Trying to use Dijkstra or BFS when the graph is a DAG with weights. Both are wrong here -- use toposort + DP.
• Forgetting to initialize unreachable nodes to $-\mathrm{\infty }$ (for longest path) or $+\mathrm{\infty }$ (for shortest path). If you initialize to 0, every node appears reachable with distance 0.
• Not reconstructing the path when the problem asks for it. Store a par[v] array alongside the DP.

---

Visual Intuition

Consider this 6-node DAG with weighted edges. We want the longest path from node 1 to node 6.

                  3         2
      1 -------> 2 -------> 5
      |          |           |
      | 1        | 4         | 6
      v          v           v
      3 -------> 4 -------> 6
           2          5

Edges and weights:

  1 -> 2  (w=3)      2 -> 4  (w=4)      4 -> 6  (w=5)
  1 -> 3  (w=1)      2 -> 5  (w=2)      5 -> 6  (w=6)
                      3 -> 4  (w=2)

One valid topological order: 1, 2, 3, 4, 5, 6. We sweep through it.

  Initialization:
  dp[1]=0   dp[2]=-inf   dp[3]=-inf   dp[4]=-inf   dp[5]=-inf   dp[6]=-inf

  Process node 1 (outgoing: 2, 3):
    dp[2] = max(-inf, dp[1]+3) = max(-inf, 3) = 3
    dp[3] = max(-inf, dp[1]+1) = max(-inf, 1) = 1

  dp[1]=0   dp[2]=3   dp[3]=1   dp[4]=-inf   dp[5]=-inf   dp[6]=-inf

  Process node 2 (outgoing: 4, 5):
    dp[4] = max(-inf, dp[2]+4) = max(-inf, 7) = 7
    dp[5] = max(-inf, dp[2]+2) = max(-inf, 5) = 5

  dp[1]=0   dp[2]=3   dp[3]=1   dp[4]=7   dp[5]=5   dp[6]=-inf

  Process node 3 (outgoing: 4):
    dp[4] = max(7, dp[3]+2) = max(7, 3) = 7      <-- no change

  dp[1]=0   dp[2]=3   dp[3]=1   dp[4]=7   dp[5]=5   dp[6]=-inf

  Process node 4 (outgoing: 6):
    dp[6] = max(-inf, dp[4]+5) = max(-inf, 12) = 12

  dp[1]=0   dp[2]=3   dp[3]=1   dp[4]=7   dp[5]=5   dp[6]=12

  Process node 5 (outgoing: 6):
    dp[6] = max(12, dp[5]+6) = max(12, 11) = 12   <-- no change

  dp[1]=0   dp[2]=3   dp[3]=1   dp[4]=7   dp[5]=5   dp[6]=12

Answer: longest path from 1 to 6 is 12, via 1 -> 2 -> 4 -> 6.

The entire computation was a single forward pass. Every time we processed a node, all of its predecessors were already finalized -- that is the guarantee topological order gives us.

Now consider path counting on the same DAG (unweighted -- count the number of distinct paths from 1 to 6):

  Initialization:
  cnt[1]=1   cnt[2]=0   cnt[3]=0   cnt[4]=0   cnt[5]=0   cnt[6]=0

  Process node 1 (outgoing: 2, 3):
    cnt[2] += cnt[1]  =>  cnt[2] = 1
    cnt[3] += cnt[1]  =>  cnt[3] = 1

  Process node 2 (outgoing: 4, 5):
    cnt[4] += cnt[2]  =>  cnt[4] = 1
    cnt[5] += cnt[2]  =>  cnt[5] = 1

  Process node 3 (outgoing: 4):
    cnt[4] += cnt[3]  =>  cnt[4] = 2

  Process node 4 (outgoing: 6):
    cnt[6] += cnt[4]  =>  cnt[6] = 2

  Process node 5 (outgoing: 6):
    cnt[6] += cnt[5]  =>  cnt[6] = 3

Answer: there are 3 distinct paths from 1 to 6:

  Path 1:  1 -> 2 -> 4 -> 6
  Path 2:  1 -> 2 -> 5 -> 6
  Path 3:  1 -> 3 -> 4 -> 6

Same graph, same toposort, different recurrence. The structure is identical.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
vector<vector<pair<int,int>>> adj(n)	<vector>	Weighted adjacency list (neighbor, weight)	$O(n+m)$ space
vector<vector<int>> adj(n)	<vector>	Unweighted adjacency list	$O(n+m)$ space
vector<long long> dp(n, LLONG_MIN)	<vector>, <climits>	DP array for longest path ($-\mathrm{\infty }$ init)	$O(n)$
vector<long long> dp(n, LLONG_MAX)	<vector>, <climits>	DP array for shortest path ($+\mathrm{\infty }$ init)	$O(n)$
queue<int> q	<queue>	BFS queue for Kahn's toposort	$O(1)$ push/pop
vector<int> indeg(n, 0)	<vector>	In-degree array for Kahn's	$O(n)$
vector<int> par(n, -1)	<vector>	Parent pointer for path reconstruction	$O(n)$

---

Implementation (Contest-Ready)

Minimal Template -- Longest Path in DAG

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n + 1);
    vector<int> indeg(n + 1, 0);

    for(int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        indeg[v]++;
    }

    // Kahn's toposort
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(indeg[i] == 0) q.push(i);
    vector<int> order;
    while(!q.empty()){
        int u = q.front(); q.pop();
        order.push_back(u);
        for(auto [v, w] : adj[u])
            if(--indeg[v] == 0) q.push(v);
    }

    // DP sweep
    vector<long long> dp(n + 1, LLONG_MIN);
    vector<int> par(n + 1, -1);
    dp[1] = 0;
    for(int u : order)
        if(dp[u] != LLONG_MIN)
            for(auto [v, w] : adj[u])
                if(dp[u] + w > dp[v]){
                    dp[v] = dp[u] + w;
                    par[v] = u;
                }

    if(dp[n] == LLONG_MIN){
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    // Reconstruct path
    vector<int> path;
    for(int v = n; v != -1; v = par[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    cout << dp[n] << "\n";
    for(int i = 0; i < (int)path.size(); i++)
        cout << path[i] << " \n"[i + 1 == (int)path.size()];
}

Explained Version -- Longest Path in DAG

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // Weighted adjacency list. adj[u] stores pairs {v, w} for edge u->v
    // with weight w. Using 1-indexed nodes.
    vector<vector<pair<int,int>>> adj(n + 1);
    vector<int> indeg(n + 1, 0);

    for(int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        indeg[v]++;
    }

    // --- Step 1: Topological sort via Kahn's algorithm ---
    // Seed the queue with all nodes that have in-degree 0.
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(indeg[i] == 0) q.push(i);

    vector<int> order;
    while(!q.empty()){
        int u = q.front(); q.pop();
        order.push_back(u);
        for(auto [v, w] : adj[u])
            if(--indeg[v] == 0) q.push(v);
    }

    // --- Step 2: DP in topological order ---
    // dp[v] = length of longest path from node 1 to node v.
    // Initialize to -infinity (unreachable). Source node gets 0.
    vector<long long> dp(n + 1, LLONG_MIN);
    vector<int> par(n + 1, -1);  // par[v] = predecessor on best path
    dp[1] = 0;

    for(int u : order){
        // Skip unreachable nodes. If dp[u] is still -inf, no path
        // from source reaches u, so nothing to propagate.
        if(dp[u] == LLONG_MIN) continue;

        for(auto [v, w] : adj[u]){
            // Relaxation: can we improve the best known path to v
            // by going through u?
            if(dp[u] + w > dp[v]){
                dp[v] = dp[u] + w;
                par[v] = u;  // remember where we came from
            }
        }
    }

    // --- Step 3: Output ---
    if(dp[n] == LLONG_MIN){
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    // Reconstruct: walk par[] backwards from sink to source.
    vector<int> path;
    for(int v = n; v != -1; v = par[v])
        path.push_back(v);
    reverse(path.begin(), path.end());

    cout << dp[n] << "\n";
    for(int i = 0; i < (int)path.size(); i++)
        cout << path[i] << " \n"[i + 1 == (int)path.size()];
}

Minimal Template -- Path Counting in DAG

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);

    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> order;
    while(!q.empty()){
        int u = q.front(); q.pop();
        order.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 : order)
        for(int v : adj[u])
            cnt[v] = (cnt[v] + cnt[u]) % MOD;

    cout << cnt[n] << "\n";
}

---

Operations Reference

Every step -- toposort, DP sweep, path reconstruction -- is linear. The total cost is dominated by reading the graph.

Operation	Time	Space
Build adjacency list + in-degrees	$O(n+m)$	$O(n+m)$
Kahn's topological sort	$O(n+m)$	$O(n)$
DP sweep (longest/shortest path)	$O(n+m)$	$O(n)$
DP sweep (path counting)	$O(n+m)$	$O(n)$
Path reconstruction via par[]	$O(n)$	$O(n)$
Total (toposort + DP)	$O(n+m)$	$O(n+m)$

All operations are linear in the size of the graph. This is optimal -- you must read every edge at least once.

---

Problem Patterns & Tricks

Pattern 1: Longest Path in a DAG

The most direct application. Given a weighted DAG, find the longest (or heaviest) path from source to sink. Process nodes in topological order, relax with max. This replaces Dijkstra/Bellman-Ford entirely on DAGs and runs in $O(n+m)$.

If edges are unweighted, treat all weights as 1 (or equivalently, count edges on the path).

dp[source] = 0;
for(int u : order)
    if(dp[u] != LLONG_MIN)
        for(auto [v, w] : adj[u])
            dp[v] = max(dp[v], dp[u] + w);

CF examples: CSES Longest Flight Route (1680), CF 721C

---

Pattern 2: Shortest Path in a DAG

Identical structure, replace max with min, initialize $dp$ to $+\mathrm{\infty }$ instead of $-\mathrm{\infty }$. This handles negative edge weights -- something Dijkstra cannot do.

vector<long long> dp(n + 1, LLONG_MAX);
dp[source] = 0;
for(int u : order)
    if(dp[u] != LLONG_MAX)
        for(auto [v, w] : adj[u])
            dp[v] = min(dp[v], dp[u] + w);

CF examples: CSES Investigation (1202) (combine shortest path with counting), CF 1272E

---

Pattern 3: Counting Paths from Source to Sink

Replace the max/min with summation. $cnt[v]=\sum _{(u,v)\in E}cnt[u]$. Initialize $cnt[source]=1$. This counts the total number of distinct paths and works modulo a prime when counts overflow.

vector<long long> cnt(n + 1, 0);
cnt[source] = 1;
for(int u : order)
    for(int v : adj[u])
        cnt[v] = (cnt[v] + cnt[u]) % MOD;

CF examples: CSES Game Routes (1681), CF 1547E

---

Pattern 4: Multi-Criteria DP on DAG

Some problems ask you to optimize multiple quantities simultaneously -- for example, find the shortest path, and among all shortest paths, the one with the most edges, and also count how many shortest paths exist. Each quantity gets its own DP array, all updated in the same toposort sweep.

// CSES Investigation: shortest dist, path count, min edges, max edges
vector<long long> dist(n + 1, LLONG_MAX);
vector<long long> cnt(n + 1, 0);
vector<int> mn(n + 1, INT_MAX), mx(n + 1, 0);
dist[1] = 0; cnt[1] = 1; mn[1] = 0; mx[1] = 0;

for(int u : order){
    if(dist[u] == LLONG_MAX) continue;
    for(auto [v, w] : adj[u]){
        long long nd = dist[u] + w;
        if(nd < dist[v]){
            dist[v] = nd;
            cnt[v] = cnt[u];
            mn[v] = mn[u] + 1;
            mx[v] = mx[u] + 1;
        } else if(nd == dist[v]){
            cnt[v] = (cnt[v] + cnt[u]) % MOD;
            mn[v] = min(mn[v], mn[u] + 1);
            mx[v] = max(mx[v], mx[u] + 1);
        }
    }
}

CF examples: CSES Investigation (1202), CF 1076D

---

Pattern 5: LIS as DP on an Implicit DAG

Longest Increasing Subsequence can be viewed as a DAG problem. Create a node for each array element. Add edge $i\to j$ if $i<j$ and $a[i]<a[j]$. This graph is a DAG (indices are strictly increasing). The longest path in this DAG is the LIS.

The $O(n^2)$ DP dp[j] = max(dp[i] + 1) for all $i<j$ with $a[i]<a[j]$ is exactly DP on this implicit DAG -- we just never build the graph explicitly. The $O(n\log n)$ patience sorting approach is a clever optimization, but the underlying structure is the same.

// O(n^2) LIS as explicit DAG DP
vector<int> dp(n, 1);
for(int j = 0; j < n; j++)
    for(int i = 0; i < j; i++)
        if(a[i] < a[j])
            dp[j] = max(dp[j], dp[i] + 1);
int lis = *max_element(dp.begin(), dp.end());

CF examples: CF 340D, CSES Increasing Subsequence

---

Pattern 6: Critical Path / Project Scheduling

Given $n$ tasks with durations and dependency constraints (task $u$ must finish before task $v$ starts), find the minimum total time to complete all tasks. This is the longest path in the dependency DAG, where edge weight $w(u,v)=\text{duration}(u)$. Called the "critical path" in project management.

// duration[u] = time to complete task u
// adj[u] = list of tasks that depend on u
dp[source] = duration[source];
for(int u : order)
    for(int v : adj[u])
        dp[v] = max(dp[v], dp[u] + duration[v]);
int total = *max_element(dp.begin() + 1, dp.begin() + n + 1);

CF examples: CF 721C, CF 1474D

---

Pattern 7: Constructing the DAG from the Problem

Many problems don't hand you a DAG directly. You must recognize that the problem's dependency structure forms a DAG and build it.

Examples:

• String problems: characters at positions form nodes; transitions based on matching rules create edges.
• Grid DP reframed as DAG: cells are nodes, edges go right and down. Every grid DP is a DAG DP in disguise.
• State-space DAG: add dimensions (position, carry, parity) to make a cyclic graph acyclic. If you can define a strict ordering on states, you have a DAG.

The key signal: if you can define a quantity that strictly increases (or decreases) along every edge, the graph is a DAG.

CF examples: CF 1272E, CF 1681C

---

When to Reach for This

DP on DAG is the right tool when:

• Longest or shortest path in a DAG -- runs in $O(V+E)$, faster than Dijkstra or Bellman-Ford.
• Counting paths from source to sink (modular arithmetic for large counts).
• Multi-criteria optimization -- track distance, count, min/max edges simultaneously.
• Any DP where transitions follow directed edges -- grid DP, LIS, scheduling with dependencies.
• The graph has negative edge weights -- Dijkstra fails here, but DAG DP handles it fine.

Why not the nearby alternative?

Alternative	When to prefer it instead
Dijkstra	Non-negative weights on a general (cyclic) graph
Bellman-Ford	Negative weights on a general (cyclic) graph
BFS	Unweighted shortest path (special case)

If the graph is a DAG, DP on DAG is always at least as fast as any of these.

---

Contest Cheat Sheet

+----------------------------------------------------------------+
|                    DP ON DAG CHEAT SHEET                        |
+----------------------------------------------------------------+
| WHEN TO USE:                                                   |
|   - Longest / shortest path in a DAG                           |
|   - Count paths from source to sink                            |
|   - Any DP where transitions follow DAG edges                  |
|   - Problem says "DAG" or you can prove no cycles              |
+----------------------------------------------------------------+
| RECIPE:                                                        |
|   1. Build adjacency list + in-degree array                    |
|   2. Kahn's toposort (or DFS post-order reversed)              |
|   3. Sweep toposort order, update dp[v] from predecessors      |
+----------------------------------------------------------------+
| LONGEST:  dp[v] = max(dp[u] + w)   init dp = -INF, dp[s] = 0 |
| SHORTEST: dp[v] = min(dp[u] + w)   init dp = +INF, dp[s] = 0 |
| COUNT:    dp[v] = sum(dp[u])        init dp = 0,    dp[s] = 1 |
+----------------------------------------------------------------+
| PATH RECONSTRUCTION:                                           |
|   par[v] = u when dp[v] updated; walk par[] from sink          |
+----------------------------------------------------------------+
| COMPLEXITY:  O(n + m) time and space                           |
+----------------------------------------------------------------+

---

Common Mistakes

Quick reference:

Mistake	Symptom	Fix
Initializing dp to 0 instead of -INF/+INF	Unreachable nodes appear reachable with distance 0	Use LLONG_MIN for longest, LLONG_MAX for shortest
Not verifying graph is a DAG	Kahn's produces fewer than N nodes; DP silently wrong	Check order.size() == n; if not, graph has a cycle
Processing nodes out of topological order	DP values computed from unfinished predecessors	Always toposort first, then sweep
Confusing DP on DAG with Dijkstra	Using Dijkstra on a DAG with negative weights, or DAG DP on a cyclic graph	DAG DP handles negative weights on DAGs; Dijkstra handles cycles with non-negative weights
Overflow with LLONG_MIN + w	Undefined behavior (signed overflow)	Guard: if(dp[u] == LLONG_MIN) continue;
Missing modular arithmetic in path counting	Long long overflow on graphs with exponentially many paths	Apply % MOD at every addition
Forgetting path reconstruction	Problem asks "print the route" but you only stored dp values	Add par[v] = u alongside every dp update

Wrong Initialization

For longest path, every non-source node must start at $-\mathrm{\infty }$ (LLONG_MIN), not 0. If you initialize to 0, then every node appears reachable with distance 0, which corrupts the DP. Similarly, shortest path needs $+\mathrm{\infty }$, not 0. Path counting initializes non-source nodes to 0 -- that one is fine.

Overflow with LLONG_MIN

If dp[u] == LLONG_MIN and you compute dp[u] + w, you get undefined behavior (signed overflow). Always guard:

if(dp[u] == LLONG_MIN) continue;

Or use a large-but-safe sentinel like -1e18 instead of LLONG_MIN:

const long long NEG_INF = -1e18;

1-Indexed vs 0-Indexed

Most CSES and CF problems use 1-indexed nodes. If you allocate vector<...> dp(n) instead of dp(n + 1), you will access out of bounds. Always match your array sizes to the vertex numbering scheme.

Forgetting Path Reconstruction

The problem says "print the path." You solved the DP but forgot to store par[v]. Now you need to rerun. Always read the full problem statement before coding. If it says "print the route," add par[] from the start.

Graph Has a Cycle

If the graph has cycles, toposort will not include all nodes (Kahn's produces fewer than $n$ nodes). Your DP will be wrong. Either detect the cycle and report it, or first condense SCCs into a DAG.

Multiple Sources / Disconnected DAG

If the DAG has multiple sources (nodes with in-degree 0) and you only initialize dp[1] = 0, nodes reachable only from other sources will stay at $-\mathrm{\infty }$. If the problem guarantees a single source, this is fine. Otherwise, initialize all sources.

Modular Arithmetic in Path Counting

When counting paths modulo ${10}^9+7$, make sure every addition includes the mod. Missing even one can cause overflow in long long if the graph has exponentially many paths.

cnt[v] = (cnt[v] + cnt[u]) % MOD;  // don't forget % MOD

Confusing Forward vs Reverse Edges

In the DP sweep, you iterate over outgoing edges: for each $u$ in toposort order, update all neighbors $v$. Some people try to iterate incoming edges instead -- that also works but requires storing the reverse graph. Pick one convention and stick with it.

Confusing DP on DAG with Dijkstra

DP on DAG and Dijkstra both find shortest paths, but they solve different problems:

• DP on DAG: requires acyclicity, handles negative weights, $O(V+E)$.
• Dijkstra: works on cyclic graphs, requires non-negative weights, $O((V+E)\log V)$.

If the graph is a DAG, prefer DP on DAG -- it is simpler and faster. If the graph has cycles and non-negative weights, use Dijkstra. If the graph has cycles and negative weights, use Bellman-Ford.

Before You Code

• [ ] Is the state graph actually acyclic? If not, DP won't work -- you need shortest path algorithms instead.
• [ ] Toposort computed before DP? Processing states out of topological order gives wrong results.
• [ ] Base cases initialized? Source nodes must have their DP values set before the main loop.
• [ ] Overflow check: Counting paths modulo ${10}^9+7$? Every addition needs the mod.
• [ ] Edge direction: Relaxing forward (predecessors to successors) or backward (pull from predecessors)? Both work, but be consistent.

---

Debug Exercises

Bug 1: Path count gives 0 for the destination:

vector<long long> cnt(n + 1, 0);
cnt[source] = 1;
for (int u : topo_order) {
    for (int v : adj[u]) {
        cnt[v] += cnt[u];
        cnt[v] %= MOD;
    }
}
cout << cnt[dest];  // prints 0

Answer

If the topological order doesn't start from source (e.g., there are nodes before source in topo order), those nodes have cnt = 0 and contribute nothing. This is actually correct. The real bug is likely that source appears in topo_order but its outgoing edges aren't being processed because the adjacency list is wrong, or dest is unreachable from source. Check that the graph is correctly built and source can actually reach dest.

Bug 2: DP gives wrong shortest path values:

vector<int> dist(n + 1, INF);
dist[source] = 0;
for (int u = 1; u <= n; u++) {  // iterating 1..n, not topo order!
    for (auto [v, w] : adj[u]) {
        dist[v] = min(dist[v], dist[u] + w);
    }
}

Answer

Iterating in order 1, 2, ..., n is not topological order (unless the graph happens to be numbered that way). A node might be processed before its predecessors, so dist[u] is still INF when its edges are relaxed. Fix: iterate over the actual topological order, not just 1..n.

Bug 3: Longest path with negative edge weights is wrong:

vector<int> dp(n + 1, 0);
dp[source] = 0;
for (int u : topo_order) {
    if (dp[u] == 0 && u != source) continue;  // skip "unreachable"
    for (auto [v, w] : adj[u]) {
        dp[v] = max(dp[v], dp[u] + w);
    }
}

Answer

Using dp[u] == 0 to detect "unreachable" is wrong when edges can have negative weights -- a reachable node might legitimately have a path cost of 0. Fix: initialize to dp[u] = -INF (e.g., -1e18) for all nodes except source, and check dp[u] == -INF for unreachability.

---

What Would You Do If...?

1. ...the DAG has ${10}^6$ nodes and you need both the shortest path length AND the count of shortest paths? Track two arrays: dist[] and cnt[]. When relaxing edge $u\to v$: if dist[u] + w < dist[v], update dist[v] and set cnt[v] = cnt[u]; if dist[u] + w == dist[v], add cnt[v] += cnt[u].

2. ...the graph has cycles? Then it's not a DAG, and topological sort doesn't exist. Use Bellman-Ford or Dijkstra for shortest paths, or find SCCs, condense into a DAG, then do DP on the condensed graph.

3. ...you need the actual path, not just the cost? Maintain a parent[] array. When you update dp[v] from dp[u], set parent[v] = u. Reconstruct the path by following parents backward from the destination.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Longest Flight Route	CSES	Easy (1500)	Longest path in DAG with path reconstruction
2	Game Routes	CSES	Easy (1500)	Count paths from 1 to $n$ in a DAG
3	Shortest Routes I	CSES	Easy (1500)	Shortest path (Dijkstra, but DAG approach also works)
4	Investigation	CSES	Medium (1600)	Multi-criteria: shortest dist + count + min/max edges
5	Journey	CF 721C	Medium (1600)	Longest path in DAG with edge weights and time limit
6	Substring Order I	CF 1547E	Medium (1600)	DAG reachability / path counting
7	Increasing Subsequence	CSES	Medium (1600)	LIS = longest path in implicit DAG
8	Course Schedule	CSES	Easy (1400)	Toposort foundation (warmup for DAG DP)
9	Coin Combinations II	CSES	Medium (1600)	Counting paths in an implicit DAG (coin states)
10	Longest Path	AtCoder DP-G	Medium (1600)	Direct longest path in a DAG

---

Rating Progression

CF Rating	What You Should Be Comfortable With
1200	Longest path in explicit DAG, basic path counting
1500	Multi-criteria DP on DAGs (min cost + count), recognizing implicit DAGs in DP problems
1800	DP on DAG of SCCs (condense -> toposort -> DP), DP with bitmask states forming a DAG
2100	DP on DAGs with edge weights derived from complex formulas, combining DAG DP with data structures (segtree on toposort order)

---

Historical Note

The connection between dynamic programming and shortest paths on DAGs was formalized by Richard Bellman in the 1950s. Bellman's "principle of optimality" -- that optimal solutions contain optimal sub-solutions -- is precisely the statement that shortest paths have optimal substructure, which holds automatically in DAGs due to acyclicity.

---

Related Topics

• Topological Sort -- prerequisite; provides the ordering that makes the DP work
• Dijkstra -- alternative for shortest path on non-negative weighted graphs (handles cycles)
• DFS -- DFS post-order gives an alternative toposort
• DP chapter bridge -- connecting graph DP to classical DP techniques
• Practice problems -- curated graph practice ladder

---

Further Reading

• cp-algorithms: Shortest paths in DAGs -- context for why DAG relaxation beats Bellman-Ford.
• CSES Problem Set: Graph Algorithms -- the "Graph Algorithms" section has excellent DAG DP practice.
• CF Blog: DP on DAGs and Topological Sort -- community discussion with examples.
• AtCoder Educational DP Contest -- Problem G is a clean DAG longest path.
• See: 02-dp-intro-1d.md for the 1D DP foundations -- every 1D DP is secretly a DAG DP on a chain.
• See: 08-dp-on-trees.md for DP when the DAG is specifically a rooted tree.

---

Recap

• DP on DAG = toposort + one forward sweep. No priority queues, no relaxation loops -- just process nodes in topological order.
• Three core variants: longest path (max), shortest path (min), path counting (sum). Same skeleton, different recurrence.
• O(V + E) time -- optimal, since you must read every edge at least once.
• Every DP you have written is secretly a DAG DP. States are nodes, transitions are edges, and your computation order is a topological sort.
• Classic traps: wrong initialization (0 vs -INF), overflow with LLONG_MIN, forgetting path reconstruction, not verifying acyclicity.
• Mnemonic: "Every DP is a DAG in disguise." See the graph, and the DP writes itself.