一, 题目说明
题目 337. House Robber III, 所有的房子连成二叉树状, 不能 "抢" 直连的两个房间, 请问最多可以抢到多少. 难度是 Medium!
二, 我的解答
惭愧, 这个题目思路始终不对. 提交了 n 次也不正确, 看了正确的思路: 爷爷节点能偷到的最大钱 = max(4 个孙子偷的钱 + 爷爷的钱, 两个儿子能偷的钱)
- class Solution{
- public:
- //recursive + memo
- int rob(TreeNode* root){
- if(root==NULL){
- return 0;
- }
- ump.clear();
- return dfs(root);
- }
- int dfs(TreeNode*root){
- if(root==NULL) return 0;
- if(ump.count(root)>0){
- return ump[root];
- }
- int money = root->val;
- if(root->left!=NULL){
- money += dfs(root->left->left) + dfs(root->left->right);
- }
- if(root->right!=NULL){
- money += dfs(root->right->left) + dfs(root->right->right);
- }
- int result = max(money,dfs(root->left)+dfs(root->right));
- ump[root] = result;
- return result;
- }
- private:
- unordered_map<TreeNode*,int> ump;
- };
- Runtime: 16 ms, faster than 81.99% of C++ online submissions for House Robber III.
- Memory Usage: 23.1 MB, Less than 55.56% of C++ online submissions for House Robber III.
三, 优化措施
当然还有其他思路, 略!
来源: http://www.bubuko.com/infodetail-3510389.html