C++ Brute Force --> Optimized DP Solutions || Explained
Approach:\n\n if we rob the ith level then we can\'t rob the i+1 th level and hence we move to the (i+2)th level\n\t ans = root->val + rob(root->left->left) + r
**Approach:**\n\n* if we rob the ith level then we can\'t rob the i+1 th level and hence we move to the (i+2)th level\n\t* ```ans = root->val + rob(root->left->left) + rob(root->left->right) + rob(root->right->left) + rob(root->right->right)```\n* if we don\'t rob the ith level then we move to the (i+1)th level\n\t* ```ans = rob(root->left) + rob(root->right)```\n* final ans will be the maximum of above two cases\n\n\n**Brute force:**\n\n```\nclass Solution\n{\npublic:\n    int rob(TreeNode *root)\n    {\n        if (root == NULL)\n            return 0;\n        int val = 0;\n        if (root->left != NULL)\n            val += rob(root->left->left) + rob(root->left->right);\n        if (root->right != NULL)\n            val += rob(root->right->left) + rob(root->right->right);\n        int notrob = rob(root->left) + rob(root->right);\n        int rob = val + root->val;\n        return max(notrob, rob);\n    }\n};\n```\n\n* we can observe that there are some repetitive calls in the above code and that\'s why it gives TLE\n* so we can just store the optimal answer we get for each node in a map\n* return the value if it has been already computed\n* otherwise follow the same approach\n* in the below code,\n\t* x = notrob case\n\t* y = rob the root case\n\n\n\n**DP**\n\n```\nclass Solution\n{\npublic:\n    unordered_map<TreeNode *, int> mp;\n    int rob(TreeNode *root)\n    {\n        if (root == NULL)\n            return 0;\n        if (mp.find(root) != mp.end())\n            return mp[root];\n        mp[root] = -1;\n        int x = rob(root->left) + rob(root->right);\n        int y = root->val;\n        if (root->left != NULL)\n            y += rob(root->left->left) + rob(root->left->right);\n        if (root->right != NULL)\n            y += rob(root->right->left) + rob(root->right->right);\n        mp[root] = max(x, y);\n        return mp[root];\n    }\n};\n```\n\n* we can see that we only have two options at each node either rob the node or not\n* if we rob the root\n\t* then we don\'t want to rob the left and right child\n\t* ```ans = root->val + leftnotrob+ rightnotrob```\n* if we don\'t rob the root\n\t* we will check what\'s the best case for the left and right child, whether to rob them or not\n\t* ```ans = max(leftnotrob, leftrob) + max(rightnotrob, rightrob```\n* store these values in a pair to handle repetitive calls\n* ```pair = {notrob,rob}```\n\n\n**DP-space optimized:**\n\n```\nclass Solution\n{\npublic:\n    unordered_map<TreeNode *, int> mp;\n    int rob(TreeNode *root)\n    {\n        if (root == NULL)\n            return 0;\n        auto ans = dfs(root);\n        return max(ans.first, ans.second);\n    }\n    pair<int, int> dfs(TreeNode *root)\n    {\n        if (root == NULL)\n            return {0, 0};\n        auto [leftnotrob, leftrob] = dfs(root->left);\n        auto [rightnotrob, rightrob] = dfs(root->right);\n        int notrob = max(leftnotrob, leftrob) + max(rightnotrob, rightrob);\n        int rob = root->val + leftnotrob + rightnotrob;\n        return {notrob, rob};\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Recursion', 'Memoization', 'C', 'C++']