C++ | with and without memo | Detailed explaination
So, robber is active again , let\'s see how we can calculate an efficient robbery !!\n\nThis again is a classic DFS problem where we have to look out for the re
So, robber is active again , let\'s see how we can calculate an efficient robbery !!\n\nThis again is a classic **DFS** problem where we have to look out for the recurrence relation and think dynamically ... The houses are present in the form of binary tree and if we are at the root_house then we have two choices :: \n**/a. to the rob the root house and skip it\'s children and move on to root\'s grandchildren.../**     OR     **/b. to skip this house and move on to left and right_subtree, with the hope that it will yeild better result./**\n   * In case robber is robbing the *root_house*,    maximum money he is gonna rob == **root->val + answer(root->left->left + root->left->right + root->right->left + root->right->right)**{as then these nodes are gonna be the grandchildren of curr_root (in case they exist)}..\n   * In case he is not robbing the *root_house*, maximum money he gonna rob == **answer(root->left + root->right)**.\n   * And Final answer == **max(root_included, root_excluded)**\n   * We are ready with the approach , just need to write base case and do recursion calls and then some calculations ... But before blindly making recursion calls , we should check out if we are calling on the same node multiple times or not !! If multiple calls on same is done, then Time Complexity would get screwed and we will have to memoize the solution !!\n   * ![image](https://assets.leetcode.com/users/images/2f063a24-f0b5-4f9f-b95c-24f38ed5fdec_1638668481.2415957.jpeg)\n   * Here , in this example we can see that::\n   *   When we include(root) , then it calls on (nodes with value 1,3 and 1) .... And when node with the value 4 will be the root and we will be excluding it , then it will call on those same nodes with value(1 and 3).... So memoization would be perfect way to go for this problem.....\n   *   **Now we know, what calls to make , what calculation to do and we also know that we need to memoize**.... So here is the code for that !!!\n   \n\n### Solution 1 ... with MEMO \n```\nclass Solution {\n\nprivate:\n    unordered_map<TreeNode*,int>memo;\n    int helper(TreeNode* root) {\n        if (root == NULL) return 0;\n        \n        if (memo.count(root)){\n            return memo[root];\n        } \n    \n        int ans_including_root = root->val;\n    \n        if (root->left != NULL) {\n              ans_including_root += helper(root->left->left) + helper(root->left->right);\n        }\n    \n        if (root->right != NULL) {\n              ans_including_root += helper(root->right->left) + helper(root->right->right);\n        }\n        \n        int ans_excluding_root = helper(root->left) + helper(root->right);\n    \n        int ans = max(ans_including_root , ans_excluding_root);\n        \n        memo[root]=ans;\n    \n        return ans;\n   }\n    \npublic:\n    int rob(TreeNode* root) {\n        return helper(root);\n    }    \n};\n```\n\nIt\'s a good solution to come up with ... But why to use memo when we can have a better solution without it ? \n* Why was the memoization needed  ? Because we were going Top Down and we weren\'t sure whether to include the root_house at that instance or not .... So , we were making recursion calls for both cases , which led to the complication of situation and we had to cover it up with the map !!\n* So , instead of going that Top-down way , let\'s try going the deepest and then while returning back, we will decide whether to choose that house or not !\n* **We will return the Pair here, {case_when_curr_root_is_chosen, case_when_not_chosen}** ... \n  * Let\'s assume any particular node (H), gets the answer from it\'s left child as {a,b} and right child as{x,y} ....\n  * So , b is the case when H->left was not included and y is the case when H->right was not included... So, if we are gonna rob the House (H) , then total money we can get, p == **H->val +y+b**\n  * And when House will be not robbed then maximum money robbed, q == **max(a,b) + max(x,y)**..... and what this node H will return is {p,q}\n \n \n###  Solution 2 -- without memo\n```\nclass Solution {\nprivate:\n    pair<int,int> max_money_robbed(TreeNode* root){\n        \n        if(root==NULL)return {0,0};\n        \n        pair<int,int>left = max_money_robbed(root->left);\n        pair<int,int>right = max_money_robbed(root->right);\n        \n        int root_house_robbed = left.second + right.second + root->val;\n        int root_house_not_robbed = max(left.first,left.second)+ max(right.first,right.second);\n        \n        pair<int,int>ans;\n        \n        ans.first = root_house_robbed, ans.second = root_house_not_robbed;\n        \n        return ans;\n        \n    }\npublic:\n    int rob(TreeNode* root) {\n        pair<int,int>result = max_money_robbed(root);\n        return max(result.first,result.second);\n    }\n};\n\n**If you reached here, Thanks for giving it a read !!**\n      \n\n\n   \n
['Dynamic Programming', 'Tree', 'Memoization', 'C']