बाइनरी ट्री में असन्निकट नोड्स का अधिकतम योग खोजने के लिए डायनामिक प्रोग्रामिंग (ट्री DP) दृष्टिकोण।
दो DP सरणियाँ: dp1[node] = नोड शामिल करने पर अधिकतम योग, dp2[node] = नोड बाहर करने पर अधिकतम योग।
उदाहरण: ट्री मान {10,5,11,6,8} के लिए अधिकतम योग 25।
C++ कार्यान्वयन
#include <bits/stdc++.h> using namespace std; void dfs(int node, int parent, int dp1[], int dp2[], list* adj, int tree[]) { int sum1 = 0, sum2 = 0; for (auto i = adj[node].begin(); i != adj[node].end(); ++i) { if (*i == parent) continue; dfs(*i, node, dp1, dp2, adj, tree); sum1 += dp2[*i]; sum2 += max(dp1[*i], dp2[*i]); } dp1[node] = tree[node] + sum1; dp2[node] = sum2; } int main() { int n = 5; list * adj = new list [n + 1]; adj[1].push_back(2); adj[2].push_back(1); adj[1].push_back(3); adj[3].push_back(1); adj[2].push_back(4); adj[4].push_back(2); adj[2].push_back(5); adj[5].push_back(2); int tree[n + 1] = {0, 10, 5, 11, 6, 8}; int dp1[n + 1], dp2[n + 1]; memset(dp1, 0, sizeof dp1); memset(dp2, 0, sizeof dp2); dfs(1, 1, dp1, dp2, adj, tree); cout << "Maximum sum: " << max(dp1[1], dp2[1]) << endl; return 0; }
आउटपुट
Maximum sum: 25