dp soln✅ | step-by-step-easy-video-explanation👁️ | O(n)🔥|
Challenge Company 4 : Flipkart\n#ReviseWithArsh #6Companies30Days Challenge 2023\nQ15. House Robber - Very Imp.\n\nhttps://youtu.be/vOJXQ_mKFoQ\nIf you found th
***Challenge Company 4 : Flipkart\n#ReviseWithArsh #6Companies30Days Challenge 2023\nQ15. House Robber - Very Imp.***\n\nhttps://youtu.be/vOJXQ_mKFoQ\n***If you found this video helpful, please consider supporting the hard work behind it. Your support would be greatly appreciated^_^***\n\n# Intuition\nDynamic Programming.\n\n# Approach\nThe key idea is to use recursion to break the problem down into subproblems and to use memoization to avoid redundant computation.\n\n# Complexity\n- Time complexity: O(n)\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    unordered_map<TreeNode*, int> lookup; // create a lookup table to store the results of subproblems\n    int rob(TreeNode* root) {\n        return helper(root);\n    }\n    int helper(TreeNode* node) {\n        if (!node) // if the input node is null, return 0\n            return 0;\n        if (lookup.count(node)) // if the result is already in the lookup table, return the value stored in the lookup table\n            return lookup[node];\n        int left = helper(node->left); // calculate the maximum amount of money that can be robbed from the left subtree\n        int right = helper(node->right); // calculate the maximum amount of money that can be robbed from the right subtree\n        int left_grandchild = helper(node->left ? node->left->left : nullptr) + helper(node->left ? node->left->right : nullptr);\n        // calculate the maximum amount of money that can be robbed from the left subtree\'s grandchild\n        int right_grandchild = helper(node->right ? node->right->left : nullptr) + helper(node->right ? node->right->right : nullptr);\n        // calculate the maximum amount of money that can be robbed from the right subtree\'s grandchild\n        int result = max(node->val + left_grandchild + right_grandchild, left + right);\n        // To avoid alerting the police, the thief cannot rob both the current node and its immediate children.\n        // Therefore, the maximum amount of money that can be robbed from the current node is the maximum of the following two options:\n        // 1. The maximum amount of money that can be robbed from the left subtree + the maximum amount of money that can be robbed from the right subtree.\n        // 2. The value of the current node + the maximum amount of money that can be robbed from the left subtree\'s grandchild + the maximum amount of money that can be robbed from the right subtree\'s grandchild.\n        lookup[node] = result; // store the result in the lookup table\n        return result;\n    }\n};\n\n```\n![upvotee.jpg](https://assets.leetcode.com/users/images/312c3619-6ac4-47fc-a29f-7baa9d4fc683_1674019461.7007656.jpeg)\n\n
['Dynamic Programming', 'Tree', 'Recursion', 'C++']