Tổng lớn nhất các nút cây nhị phân không liền kề | Quy hoạch động trong C++

Bài toán tương tự nhưng dùng DP trên cây với 2 trạng thái dp1 (chọn) và dp2 (không chọn), duyệt DFS post-order.

Thuật toán

• dp1[u] = val[u] + sum(dp2[v]) cho mọi con v.
• dp2[u] = sum(max(dp1[v], dp2[v])) cho mọi con v.
• Kết quả: max(dp1[root], dp2[root]).

Ví dụ triển khai (C++)

#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 (int v : adj[node]) {
        if (v == parent) continue;
        dfs(v, node, dp1, dp2, adj, tree);
        sum1 += dp2[v];
        sum2 += max(dp1[v], dp2[v]);
    }
    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] = {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;
}

Đầu ra

Maximum sum: 25