Tìm tổng lớn nhất các nút trong cây nhị phân sao cho không có hai nút nào liền kề bằng quy hoạch động C++

Trong bài toán này, chúng ta được cung cấp một Cây Nhị Phân với mỗi nút có một giá trị. Nhiệm vụ là viết chương trình tìm Tổng lớn nhất của các nút trong Cây nhị phân sao cho không có hai nút nào liền kề nhau sử dụng Quy hoạch động.

Mô tả bài toán

Chúng ta sẽ chọn tập con các nút của cây nhị phân để tổng lớn nhất sao cho các nút không được nối trực tiếp với nhau (không được chọn cả cha và con).

Ví dụ minh họa

Đầu vào

Đầu ra

24

Giải thích

Các nút được chọn: 8 + 5 + 9 + 2 = 24

Phương pháp giải

Giải pháp sử dụng bản đồ (map) để tìm tổng các nút tạo thành maxSum. Cả nút cha và nút con không thể cùng được chọn. Do đó, trước khi chọn một nút, ta cần kiểm tra xem cây con của nó có tạo thành tổng lớn hơn hay không.

Việc tính toán lặp lại tổng của cùng một cây con cha-con cho nhiều nút sẽ làm tăng chi phí tính toán. Để khắc phục, ta sử dụng kỹ thuật ghi nhớ (memoization) và lưu trữ maxSum tính đến nút đó trong một map để sử dụng sau này.

Chương trình minh họa

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

struct node {
    int data;
    struct node *left, *right;
};

struct node* newNode(int data) {
    struct node *temp = new struct node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int findMaxSumBT(node* node, map<struct node*, int>& nodeSum);

int sumSubTreeNodes(node* node, map<struct node*, int>& nodeSum) {
    int maxSum = 0;
    if (node->left)
        maxSum += findMaxSumBT(node->left->left, nodeSum) +
                  findMaxSumBT(node->left->right, nodeSum);
    if (node->right)
        maxSum += findMaxSumBT(node->right->left, nodeSum) +
                  findMaxSumBT(node->right->right, nodeSum);
    return maxSum;
}

int findMaxSumBT(node* node, map<struct node*, int>& nodeSum) {
    if (node == NULL)
        return 0;
    if (nodeSum.find(node) != nodeSum.end())
        return nodeSum[node];
    
    int sumInclCurr = node->data + sumSubTreeNodes(node, nodeSum);
    int sumExclCurr = findMaxSumBT(node->left, nodeSum) +
                      findMaxSumBT(node->right, nodeSum);
    
    nodeSum[node] = max(sumInclCurr, sumExclCurr);
    return nodeSum[node];
}

int main() {
    node* root = newNode(9);
    root->left = newNode(4);
    root->right = newNode(7);
    root->left->left = newNode(8);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    
    map<struct node*, int> nodeSum;
    cout << "Tổng lớn nhất các nút trong cây nhị phân không liền kề nhau bằng DP là "
         << findMaxSumBT(root, nodeSum);
    return 0;
}

Đầu ra

Tổng lớn nhất các nút trong cây nhị phân không liền kề nhau bằng DP là 24