Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm tổng số nút tối đa trong cây nhị phân sao cho không có hai nút nào liền kề bằng cách sử dụng Lập trình động.
Đối với điều này, chúng tôi sẽ được cung cấp một cây nhị phân. Nhiệm vụ của chúng tôi là tìm tập hợp con có tổng lớn nhất sao cho không có hai nút nào trong tập hợp con được kết nối trực tiếp bằng Lập trình động.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
//finding diameter using dynamic programming
void dfs(int node, int parent, int dp1[], int dp2[], list<int>* 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<int>* adj = new list<int>[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];
tree[1] = 10;
tree[2] = 5;
tree[3] = 11;
tree[4] = 6;
tree[5] = 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;
} Đầu ra
Maximum sum: 25