Maximum sum of nodes in Binary tree such that no two are adjacent | Dynamic Programming In C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมหาผลรวมสูงสุดของโหนดในต้นไม้ไบนารี โดยที่ไม่มีสองโหนดติดกัน ใช้ Dynamic Programming

เราจะได้รับต้นไม้ไบนารี งานคือหาซับเซ็ตผลรวมสูงสุดที่ไม่มีโหนดติดกัน โดยใช้ DP บนกราฟต้นไม้ (Tree DP)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

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;
}

เอาต์พุต

Maximum sum: 25