Cướp nhà III trong C++

Cây nhị phân đại diện khu nhà, gốc là cửa vào. Không thể cướp 2 nhà liên trực tiếp (cha-con). Tìm tiền tối đa có thể cướp.

Ví dụ: cây [3,2,3,null,3,null,1] → Kết quả: 7.

Giải thuật (DP trên cây)

1. Hàm solve(node) trả về cặp (cantBeAdded, canBeAdded):
2. cantBeAdded: tiền nếu cướp nút này (không cướp con).
3. canBeAdded: tiền tối đa nếu không cướp nút này (có thể cướp con hoặc không).
4. Nếu node null → (-INF, 0).
5. Đệ quy lấy leftVal, rightVal, lấy max với 0.
6. cantBeAdded = max(node->val,0) + leftVal.second + rightVal.second.
7. canBeAdded = max(leftVal.first+rightVal.first, max(leftVal.second, rightVal.second, leftVal.second+rightVal.second, leftVal.second+rightVal.first, rightVal.second+leftVal.first)).
8. Kết quả: max(solve(root).first, solve(root).second).

Ví dụ C++

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

class TreeNode {
public:
    int val; TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q; q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front(); q.pop();
        if(!temp->left) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0); return;
        } else q.push(temp->left);
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0); return;
        } else q.push(temp->right);
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) insert(&root, v[i]);
    return root;
}

const int INF = -1e8;

class Solution {
public:
    pair<int,int> solve(TreeNode* node) {
        if(!node) return {INF, 0};
        auto leftVal = solve(node->left);
        auto rightVal = solve(node->right);
        leftVal.first = max(leftVal.first, 0);
        leftVal.second = max(leftVal.second, 0);
        rightVal.first = max(rightVal.first, 0);
        rightVal.second = max(rightVal.second, 0);
        int currentVal = max(node->val, 0);
        int cantBeAdded = currentVal + leftVal.second + rightVal.second;
        int canBeAdded = max(leftVal.first + rightVal.first, max({
            leftVal.second, rightVal.second,
            leftVal.second + rightVal.second,
            leftVal.second + rightVal.first,
            rightVal.second + leftVal.first
        }));
        return {cantBeAdded, canBeAdded};
    }
    int rob(TreeNode* root) {
        auto a = solve(root);
        return max(a.first, a.second);
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,2,3,NULL,3,NULL,1};
    TreeNode *root = make_tree(v);
    cout << ob.rob(root);
    return 0;
}

Đầu vào

[3,2,3,null,3,null,1]

Đầu ra

7