DP on DAGs

Every DP is a DAG problem: the states are vertices, the transitions are edges, and the required evaluation order is a topological order. Making that explicit is often the clearest way to think about a DP — and it is the only correct way when the state graph is given as an actual graph.

The equivalence

DP language	Graph language
state	vertex
transition	edge
base case	source with a fixed value
evaluation order	topological order
optimal substructure	shortest/longest path
cyclic dependency	not a DAG — needs Dijkstra or Bellman-Ford

The last row is the practical payoff: if you find your DP states depend on each other cyclically, you have not made a mistake in the DP — you have discovered that the problem is a shortest-path problem, and you should switch algorithms.

The template

vector<int> order = topoSort(n, adj);
for (int u : order)
    for (auto [v, w] : adj[u])
        dp[v] = max(dp[v], dp[u] + w);          // or min, or +=, or *=

What it computes

Question	Recurrence
Longest path	`dp[v] = max(dp[u] + w)`
Shortest path (negatives fine)	`dp[v] = min(dp[u] + w)`
Number of paths $s \to t$	`cnt[v] += cnt[u]`
Number of shortest paths	carry a count; reset on strict improvement
Longest path ending at each vertex	the DP array itself
Reachability from $v$	reverse order, union of successor bitsets
Minimum path cover	$n$ − bipartite matching
Lexicographically smallest longest path	tie-break by vertex label during relaxation

DAGs hiding in plain sight

Most classical DPs are DAG longest-path problems in disguise:

Problem	The DAG
Grid paths	cells; edges right and down
LCS	$(i, j)$ pairs; edges advance one or both indices
LIS	indices; edge $i \to j$ when $i < j$ and $a_{i} < a_{j}$
Knapsack	$(item, capacity)$
Interval DP	intervals; edges to shorter sub-intervals
Bitmask DP	subsets; edges add one element
Course scheduling	prerequisites
Build systems	dependencies

Recognising the DAG tells you the complexity immediately: states × transitions.

When the graph has cycles: condense first

Contract strongly connected components to get a DAG, then run the DP on it. Inside an SCC you can move freely, so the component contributes all of its vertices at once. See Condensation Graph.

“Maximum total value collectible on a walk” → condense, weight each component by its internal total, take the longest path.

Longest path is easy here, hard in general

Longest path in a general graph is NP-hard (it contains Hamiltonian path as a special case). On a DAG it is linear. The reason is exactly optimal substructure: with no cycles, an optimal path to $v$ extends an optimal path to some predecessor, which is false in a graph with cycles because reusing vertices is forbidden.

Counting paths and the modulus

Path counts explode, so problems ask for the count mod a prime. Two things to watch:

Zero-weight cycles are still cycles — check that the graph is genuinely acyclic before counting.
Unreachable states should not contribute; initialise carefully (0 for counts, $- \infty$ for maxima, and skip unreachable states in the relaxation).

Path reconstruction

Store par[v] on each improving relaxation, then walk back from the best endpoint. For lexicographic requirements, break ties on the parent’s label at relaxation time rather than trying to fix it afterwards.

whoashish's cp notes

Directory