When to Use DP on Graphs
DP on graphs works when the graph has structure that prevents cycles in the DP recurrence: DAGs (directed acyclic graphs), trees, or layered graphs. For general graphs with cycles, DP requires bitmask over visited nodes (TSP). Key insight: topological order on a DAG gives the computation order for DP — process nodes in topological order, referencing already-computed values for predecessors.
Bellman-Ford: DP on General Graphs
Shortest path with negative edges. dp[k][v] = minimum distance to reach v using at most k edges. Recurrence: dp[k][v] = min(dp[k-1][v], min over all edges (u,v): dp[k-1][u] + weight(u,v)). Run for k = 1..n-1 iterations. If dp[n][v] < dp[n-1][v] for any v: negative cycle detected. Time: O(V*E). Space optimization: use a single array and relax in place (but lose the "at most k edges" property). Bellman-Ford is a DP on the graph structure — each iteration relaxes one more "hop".
def bellman_ford(n, edges, src):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# check negative cycle
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # negative cycle
return distDAG DP: Longest Path
Longest path in a DAG (NP-hard for general graphs, polynomial for DAGs). Topological sort first, then: dp[v] = max(dp[u] + weight(u,v)) for all predecessors u of v. The topological order ensures all predecessors are computed before v. Applications: critical path in project scheduling (longest path = minimum project duration), number of ways to reach a node (sum instead of max), longest increasing subsequence (reduce to DAG DP on sorted elements). LIS as DAG DP: edge from i to j if i < j and nums[i] < nums[j]; longest path = LIS length. But the O(n log n) patience sort is faster than explicit DAG DP.
Tree DP
Many tree problems require computing values that depend on subtree structure. Standard pattern: define dp[v] = some property of the subtree rooted at v. Compute by post-order DFS (leaves first). Example: maximum path sum (LC 124). For each node, compute the max gain from its left subtree and right subtree: max_gain(v) = max(0, max_gain(left)) + max(0, max_gain(right)) + val[v]. Update global max with this. Return max(0, val[v] + max(max_gain(left), max_gain(right))) — the one-sided path usable by the parent.
def max_path_sum(root):
res = [float('-inf')]
def dp(node):
if not node: return 0
left = max(0, dp(node.left))
right = max(0, dp(node.right))
res[0] = max(res[0], node.val + left + right)
return node.val + max(left, right)
dp(root)
return res[0]Tree Diameter
Diameter = longest path between any two nodes. Two approaches: (1) Two-BFS: BFS from any node to find the farthest node u; BFS from u to find the farthest node v; distance(u,v) = diameter. O(V). (2) Tree DP: for each node, diameter through that node = depth of longest path in left subtree + depth of longest path in right subtree. Post-order DFS, maintain global max. Both are O(V). The tree DP generalizes to weighted trees and is the basis for solving harder subtree problems.
Bitmask DP: Traveling Salesman Problem
Visit all n cities exactly once, minimize total distance. dp[mask][v] = minimum cost to visit exactly the cities in mask, ending at v. Transition: dp[mask | (1 << u)][u] = min over all u not in mask: dp[mask][v] + dist[v][u]. Final answer: min over all v: dp[(1<<n)-1][v] + dist[v][0]. Time: O(2^n * n^2). Space: O(2^n * n). Practical for n <= 20. Reconstruct path by storing parent pointers alongside DP values. This pattern applies to any problem asking for minimum cost to cover all elements of a small set.
Floyd-Warshall: All-Pairs Shortest Path
dp[k][i][j] = shortest path from i to j using only nodes 0..k as intermediates. Recurrence: dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]). Space optimization: update in-place (dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])). O(V^3) time, O(V^2) space. Detects negative cycles: if dp[i][i] < 0 after running, there is a negative cycle through node i. Use when you need all-pairs shortest paths or when the graph is dense.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Databricks Interview Guide