Dynamic Programming • Pattern

DP on Graphs

Understand the fundamental relationship between Dynamic Programming and Graph Theory.

The Grand Unification

Dynamic programming is just finding the shortest or longest path in a Directed Acyclic Graph (DAG).

Every subproblem (e.g. `dp[i][j]`) is a node in the graph. The number of states is the number of vertices |V|.

The recursive call (e.g. `dp[i-1][j]`) is a directed edge between nodes. The number of choices is the out-degree.

DP only works if there are no cycles (infinite loops in recursion). Hence, the graph of dependencies must be a DAG.

dp[0]

dp[1]

dp[2]

dp[3]

Code Tracker

:::

1// Conceptual connection between DP and Graphs

2// State = Node

3// Transition = Edge

4// Order of evaluation = Topological Sort

5// Shortest/Longest path = Min/Max DP