Dynamic Programming • Graphs

DP on DAGs

Dynamic Programming naturally aligns with Directed Acyclic Graphs (DAGs) since they define a strict dependency order (Topological Sort).

Try Interactive Simulator

Overview

In a DAG, there are no cycles, meaning states never depend on themselves. This guarantees that subproblems can be solved in a strict sequential order.

Topological Sort

We first find the topological order of the graph. This ensures that when we process node `u`, all possible paths to `u` have already been computed.

Transitions

For each node `u` in topological order, we relax all its outgoing edges `u -> v`: `dp[v] = max(dp[v], dp[u] + weight)`.

Key Insight

DP state transitions are just edges in a DAG! Any DP problem can be modeled as finding the shortest or longest path in a DAG of subproblems.

0

1

2

3

dp[0]0

dp[1]-inf

dp[2]-inf

dp[3]-inf

Code Tracker

:::

1let dp = Array(V).fill(-Infinity); dp[0] = 0;

2let topoOrder = topologicalSort(graph);

3for (let u of topoOrder) {

4 for (let edge of graph[u]) {

5 let v = edge.to, w = edge.weight;

6 if (dp[u] + w > dp[v]) {

7 dp[v] = dp[u] + w;

8 }

9 }

10}

Dag Dp

Dag Dp

DP on DAGs

Overview

Topological Sort

Transitions

Key Insight

DP on DAGs

Overview

Topological Sort

Transitions

Key Insight