(Dynamic Programming Beyond Arrays)
π Why DP on Trees & Graphs?
So far, we solved DP on arrays, strings, intervals. But real-world data often forms hierarchies (trees) or networks (graphs).
Here, subproblems are no longer just [iβ¦j]
or prefixesβtheyβre subtrees or graph components.
β‘ Key Idea
- On Trees β DP is usually done with DFS + memoization.
- On Graphs β DP often relies on topological ordering (for DAGs) or cycle handling.
π³ DP on Trees
π Patterns
1οΈβ£ Tree DP (Post-order DFS)
Each nodeβs result depends on its children.
Example: Diameter of a Tree (Longest Path)
class TreeDiameter {
int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return diameter;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right = dfs(node.right);
diameter = Math.max(diameter, left + right);
return 1 + Math.max(left, right);
}
}
-
dfs(node)
returns height. - Global
diameter
updates from children.
2οΈβ£ Maximum Path Sum in Binary Tree
class MaxPathSum {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, left + right + node.val);
return node.val + Math.max(left, right);
}
}
-
Notice DP relation:
dp[node] = node.val + max(dp[left], dp[right])
3οΈβ£ Tree DP with Subtree Inclusion/Exclusion (Classic βTree Knapsackβ)
π Problem: Maximum sum of nodes with constraint β cannot take both parent & child.
class HouseRobberTree {
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]);
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0,0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
// res[0] = max sum if NOT taking node
// res[1] = max sum if taking node
return new int[]{
Math.max(left[0], left[1]) + Math.max(right[0], right[1]),
node.val + left[0] + right[0]
};
}
}
4οΈβ£ LCA + DP on Trees
Lowest Common Ancestor (LCA) is a preprocessing DP using binary lifting.
class LCA {
int LOG = 20;
int[][] up;
int[] depth;
List<Integer>[] adj;
public LCA(int n, int root, List<Integer>[] adj) {
this.adj = adj;
up = new int[n][LOG];
depth = new int[n];
dfs(root, root);
}
private void dfs(int node, int parent) {
up[node][0] = parent;
for (int i = 1; i < LOG; i++) {
up[node][i] = up[up[node][i-1]][i-1];
}
for (int nei : adj[node]) {
if (nei == parent) continue;
depth[nei] = depth[node] + 1;
dfs(nei, node);
}
}
public int query(int a, int b) {
if (depth[a] < depth[b]) { int tmp=a; a=b; b=tmp; }
int diff = depth[a] - depth[b];
for (int i = LOG-1; i >= 0; i--) {
if (((diff >> i) & 1) == 1) a = up[a][i];
}
if (a == b) return a;
for (int i = LOG-1; i >= 0; i--) {
if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
}
-
DP preprocessing stores ancestors at
2^i
distance. - Query runs in
O(logN)
.
π DP on Graphs
π Patterns
1οΈβ£ Longest Path in a DAG
class LongestPathDAG {
public int longestPath(int n, int[][] edges) {
List<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
int[] indegree = new int[n];
for (int[] e : edges) {
adj[e[0]].add(e[1]);
indegree[e[1]]++;
}
Queue<Integer> q = new LinkedList<>();
int[] dp = new int[n];
for (int i = 0; i < n; i++) if (indegree[i]==0) q.add(i);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj[u]) {
dp[v] = Math.max(dp[v], dp[u] + 1);
if (--indegree[v] == 0) q.add(v);
}
}
int ans = 0;
for (int d : dp) ans = Math.max(ans, d);
return ans;
}
}
- Topological sort ensures dependencies are resolved first.
2οΈβ£ Shortest Path in DAG (DP form of Dijkstra)
class ShortestPathDAG {
public int[] shortestPath(int n, int[][] edges, int src) {
List<int[]>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) adj[e[0]].add(new int[]{e[1], e[2]});
int[] topo = topoSort(n, adj);
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int u : topo) {
if (dist[u] == Integer.MAX_VALUE) continue;
for (int[] e : adj[u]) {
int v = e[0], w = e[1];
dist[v] = Math.min(dist[v], dist[u] + w);
}
}
return dist;
}
private int[] topoSort(int n, List<int[]>[] adj) {
int[] indegree = new int[n];
for (int u = 0; u < n; u++) {
for (int[] e : adj[u]) indegree[e[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (indegree[i]==0) q.add(i);
int[] order = new int[n]; int idx=0;
while (!q.isEmpty()) {
int u = q.poll();
order[idx++] = u;
for (int[] e : adj[u]) if (--indegree[e[0]]==0) q.add(e[0]);
}
return order;
}
}
3οΈβ£ Floyd-Warshall (All-Pairs Shortest Path)
class FloydWarshall {
public void floydWarshall(int[][] dist) {
int n = dist.length;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != 1e9 && dist[k][j] != 1e9) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
}
- This is DP on graph nodes as intermediates.
π Key Insights
- Tree DP: Usually DFS-based, bottom-up.
- Graph DP: Usually topological-order DP for DAGs or matrix DP (Floyd-Warshall).
-
Subproblems:
- For trees β subtrees.
- For graphs β nodes + edges constraints.
π― Real-Life Applications
- Network routing (shortest path).
- Compilers & parsing (tree DP).
- Game AI (minimax on trees).
- Data indexing (optimal BST).
Top comments (0)