leetcode 337. House Robber III

題意

題目連結： https://leetcode.com/problems/house-robber-iii/

就是一顆樹，然後頭結點選了的話，隻能選孫子結點

然後求這個樹的可以選的最大的和

解法一

暴力+記憶化， 就是

dfs(root, can)

表示 目前root結點 可不可以被選

顯然目前節點 可以選的話 結果就是

max(root->val + dfs(root->l, notcan) + dfs(root->r, notcan), dfs(root->l, can) + dfs(root->r, can))

如果不可以選的話 結果就是

dfs(root->l, can) + dfs(root->r, can)

typedef pair<TreeNode*, bool> ptb;
class Solution {
public:
    map<ptb, int> mp;
    
    int dfs(TreeNode *root, bool can) {
        if(root==NULL) return 0;
        if(mp.count({root, can}))
            return mp[{root, can}];
        if(can) {
            mp[{root,can}] =  max(root->val + dfs(root->left, !can) + dfs(root->right, !can),
                       dfs(root->left, true)+dfs(root->right, true));
            return mp[{root, can}];
        } else {
            mp[{root,can}] = dfs(root->left, true) + dfs(root->right, true);
            return mp[{root, can}];
            // return dfs(root->left, true) + dfs(root->right, true);
        }
    }
    
    int rob(TreeNode* root) {
        if(root == NULL) return 0;
        return dfs(root, true);
    }
};                

解法二

我們使用vector來存 兩個值

v[0] 代表目前節點可以選 v[1] 代表節點不可以選的最大值

那麼很顯然同上面，直接

v[root][0] = max(root->val+v[root->l][1]+v[root->r][1], v[root->l][0]+v[root->r][0]);

v[root][1] = v[root->l][0]+v[root->r][0]

遞歸求解即可

class Solution {
public:
    
    // v[0] means rob the root, v[1] means not rob the root
    vector<int> dfs(TreeNode *root) {
        if(root == NULL)
            return {0, 0};
        vector<int> v1 = dfs(root->left);
        vector<int> v2 = dfs(root->right);
        int res1 = max(root->val + v1[1] + v2[1], v1[0]+v2[0]);
        int res2 = v1[0]+v2[0];
        return {res1, res2};
    }
    
    int rob(TreeNode* root) {
        vector<int> s = dfs(root);
        return max(s[0], s[1]);
    }
};                

轉載于:https://www.cnblogs.com/Draymonder/p/11297866.html