DP on DAGs and Graph-Based DP

What This Concept Is

Finite acyclic DP can be viewed as evaluation of a dependency DAG. Use a fixed edge convention: here an edge goes from a prerequisite state to its dependent. A topological order then computes prerequisites first. If arrows instead point from a state to what it reads, reverse that order.

Some recurrences select one predecessor and add a transition cost, so they are shortest/longest-path computations. Others combine several subsolutions at once: matrix-chain splits need both children, and tree DP sums child contributions. A dependency DAG still describes evaluation order, but ordinary single-path relaxation alone does not express those combinations.

Why It Matters Here

This connects graph traversal to recurrence evaluation without claiming every DP is an ordinary path problem. Cyclic Bellman equations and fixed-point methods exist outside the one-pass acyclic model; their termination/convergence requires additional assumptions. Adding a bounded time/edge-count coordinate can turn some cyclic input problems into acyclic state computations.

Concrete Examples

Source-specific longest path on a DAG. Initialize source distance 0 and other vertices unreachable. In topological order relax each u->v using distance[u]+weight(u,v) only if u is reachable. Signed weights are allowed. For edges 0->1:-5, 0->2:-2, 1->3:1, 2->3:-1, the longest source-to-3 distance is -3 via 2. Initializing every vertex to zero instead would permit new starts and solve a different problem. Store original parent edge IDs.

Knapsack layers. State (i,c) depends on (i-1,c) and, when legal, (i-1,c-w). Edges run from layer i-1 to i. Collapsing layers into one array requires an order that emulates those dependencies, explaining descending capacity.

Weighted intervals. Create prefix vertices 0..n. An edge (i-1)->i of weight 0 represents skipping job i-1. Edge p(i-1)->i of weight value represents taking it after a compatible prefix. Longest path from 0 to n implements the same recurrence; a chosen positive or negative edge must still be interpreted as the associated job identity. Empty selection remains possible.

Bounded walks. Bellman-Ford's snapshot state (k,v) gives the shortest walk using at most k edges. It reads only layer k-1, so the state dependency graph is acyclic even when the input graph has cycles. The distinction between an input graph and a state graph matters. In-place relaxation does not preserve the exact snapshot-per-pass interpretation.

Common Confusion / Misconceptions

Longest simple path is NP-hard in general graphs; longest unrestricted walk can instead be unbounded through a relevant positive cycle. Those are different claims. A cycle in an input graph does not rule out DP with augmented state. Satisfying local equations around a cycle does not prove a unique solution or convergence. A full topological schedule assumes acyclicity is established.

How To Use It

Name the state vertices, arrow direction, recurrence operator and rank. Distinguish selection of one predecessor from combination of several. State source and unreachable initialization. Reconstruct witnesses using valid transitions, and verify all edges if the graph is explicitly supplied. For cyclic equations, stop and derive a suitable layered formulation or a separately justified solver.

Check Yourself

Which arrow convention matches a normal topological order? Why is matrix-chain evaluation not just choosing one cheapest predecessor? What coordinate makes bounded-edge shortest paths acyclic?

Mini Drill or Application

Draw the prefix DAG for jobs (0,2,3),(2,4,3),(0,4,7) sorted by finish with ties ordered by start. Feedback: enumerate the take/skip edges and recover value 7. A different finish-tie ordering is acceptable if p only refers backward and the corresponding job IDs and dependencies are consistent.

Read This Only If Stuck

CLRS: DAG paths and dynamic-programming dependencies. Compare with the prior graph module's source-specific path contract and Bellman-Ford round semantics.