Trees पर DP

Tree DP किसी family tree की हर branch से अपने parent को एक answer report करने को कहने जैसा है, ताकि top person उन सभी को combine कर सके।

In this page:

Tree DP Idea
Postorder DP
Choose or Skip
Tree States
Practice

Syntax

markup

def dfs(node):
    if node is None:
        return (0, 0)    # (skip, take)
    left = dfs(node.left)
    right = dfs(node.right)
    take = node.value + left[0] + right[0]
    skip = max(left) + max(right)
    return (skip, take)

Tree DP Idea

Tree DP किसी tree पर defined एक problem को हर subtree के लिए एक answer compute करके solve करता है, उस subtree के children के लिए पहले से compute किए answers उपयोग करते हुए — इसलिए information leaves से root की ओर ऊपर बहती है।

उदाहरण: Tree DP Idea

#include <iostream>
using namespace std;
int main() {
	cout << "Tree DP: compute an answer for each subtree, information flows upward from leaves to root";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Tree DP: compute an answer for each subtree, information flows upward from leaves to root");
	}
}

print("Tree DP: compute an answer for each subtree, information flows upward from leaves to root")

#include <stdio.h>
int main() {
	printf("Tree DP: compute an answer for each subtree, information flows upward from leaves to root");
	return 0;
}

Postorder DP

चूंकि किसी node का answer आमतौर पर इसके children के answers पर निर्भर करता है, एक postorder traversal (parent पर वापस जाने से पहले हर child को पूरी तरह process करना) tree DP compute करने का natural तरीका है: जब आप किसी node पर results combine करने के लिए तैयार हों, हर child result पहले से available है।

उदाहरण: Postorder DP

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> children = {{1,2},{},{}};
int solve(int node) {
	int total = 0;
	for (int c : children[node]) total += solve(c);
	return total + 1;
}
int main() { cout << "Subtree size at root (children fully processed first): " << solve(0); return 0; }

import java.util.*;
public class Main {
	static List<List<Integer>> children = Arrays.asList(Arrays.asList(1,2), Arrays.asList(), Arrays.asList());
	static int solve(int node) {
		int total = 0;
		for (int c : children.get(node)) total += solve(c);
		return total + 1;
	}
	public static void main(String[] args) { System.out.println("Subtree size at root (children fully processed first): " + solve(0)); }
}

children = [[1,2],[],[]]
def solve(node):
    return sum(solve(c) for c in children[node]) + 1
print("Subtree size at root (children fully processed first):", solve(0))

#include <stdio.h>
int children[3][2] = {{1,2},{-1,-1},{-1,-1}};
int solve(int node) {
	int total = 0;
	for (int i = 0; i < 2; i++) if (children[node][i] != -1) total += solve(children[node][i]);
	return total + 1;
}
int main() { printf("Subtree size at root (children fully processed first): %d", solve(0)); return 0; }

Choose or Skip

कुछ tree DP problems, जैसे House Robber का tree version, हर node पर यह decide करना चाहिए कि उस node को take करना है (और इसलिए इसके immediate children skip करना) या इसे skip करना है (children को free में लेने देना), और DP दोनों possibilities अलग-अलग track करता है।

उदाहरण: Choose or Skip

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> children = {{1,2},{},{}};
int val[3] = {5, 3, 4};
int solveTaken(int node);
int solveSkipped(int node);
int solveTaken(int node) {
	int sum = val[node];
	for (int c : children[node]) sum += solveSkipped(c);
	return sum;
}
int solveSkipped(int node) {
	int sum = 0;
	for (int c : children[node]) sum += max(solveTaken(c), solveSkipped(c));
	return sum;
}
int main() { cout << "House Robber on a tree, best at root: " << max(solveTaken(0), solveSkipped(0)); return 0; }

import java.util.*;
public class Main {
	static List<List<Integer>> children = Arrays.asList(Arrays.asList(1,2), Arrays.asList(), Arrays.asList());
	static int[] val = {5, 3, 4};
	static int solveTaken(int node) {
		int sum = val[node];
		for (int c : children.get(node)) sum += solveSkipped(c);
		return sum;
	}
	static int solveSkipped(int node) {
		int sum = 0;
		for (int c : children.get(node)) sum += Math.max(solveTaken(c), solveSkipped(c));
		return sum;
	}
	public static void main(String[] args) { System.out.println("House Robber on a tree, best at root: " + Math.max(solveTaken(0), solveSkipped(0))); }
}

children = [[1,2],[],[]]
val = [5, 3, 4]
def solve_taken(node):
    return val[node] + sum(solve_skipped(c) for c in children[node])
def solve_skipped(node):
    return sum(max(solve_taken(c), solve_skipped(c)) for c in children[node])
print("House Robber on a tree, best at root:", max(solve_taken(0), solve_skipped(0)))

#include <stdio.h>
int children[3][2] = {{1,2},{-1,-1},{-1,-1}};
int val[3] = {5, 3, 4};
int solveTaken(int node);
int solveSkipped(int node);
int solveTaken(int node) {
	int sum = val[node];
	for (int i = 0; i < 2; i++) if (children[node][i] != -1) sum += solveSkipped(children[node][i]);
	return sum;
}
int solveSkipped(int node) {
	int sum = 0;
	for (int i = 0; i < 2; i++) if (children[node][i] != -1) {
		int c = children[node][i];
		int t = solveTaken(c), s = solveSkipped(c);
		sum += t > s ? t : s;
	}
	return sum;
}
int main() {
	int t = solveTaken(0), s = solveSkipped(0);
	printf("House Robber on a tree, best at root: %d", t > s ? t : s);
	return 0;
}

Tree States

चूंकि किसी node का best answer इस पर निर्भर कर अलग हो सकता है कि इसे select किया गया था या नहीं, कई tree DP problems प्रति node एक के बजाय दो values store करती हैं — उदाहरण के लिए dp[node][0] 'not taken' के लिए और dp[node][1] taken के लिए — और parent में merge होते समय उन्हें अलग तरीके से combine करती हैं।

उदाहरण: Tree States

#include <iostream>
using namespace std;
int main() {
	int dpTaken = 5, dpNotTaken = 7;
	cout << "Two values stored per node: dp[node][0]=not taken=" << dpNotTaken << ", dp[node][1]=taken=" << dpTaken;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int dpTaken = 5, dpNotTaken = 7;
		System.out.println("Two values stored per node: dp[node][0]=not taken=" + dpNotTaken + ", dp[node][1]=taken=" + dpTaken);
	}
}

dp_taken, dp_not_taken = 5, 7
print(f"Two values stored per node: dp[node][0]=not taken={dp_not_taken}, dp[node][1]=taken={dp_taken}")

#include <stdio.h>
int main() {
	int dpTaken = 5, dpNotTaken = 7;
	printf("Two values stored per node: dp[node][0]=not taken=%d, dp[node][1]=taken=%d", dpNotTaken, dpTaken);
	return 0;
}

Practice

Tree DP एक साथ तीन ideas combine करता है: structure में चलने के लिए recursion, हर subproblem define करने के लिए subtree boundaries, और उसी subtree के answer को एक से ज़्यादा बार recompute करने से बचने के लिए stored per-node states।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Tree DP = recursion + subtree boundaries + stored per-node states to avoid recomputation";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Tree DP = recursion + subtree boundaries + stored per-node states to avoid recomputation");
	}
}

print("Tree DP = recursion + subtree boundaries + stored per-node states to avoid recomputation")

#include <stdio.h>
int main() {
	printf("Tree DP = recursion + subtree boundaries + stored per-node states to avoid recomputation");
	return 0;
}

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson DP on Grids Next Lesson → Greedy Introduction