LeetCode 337 House Robber III

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-02-20 11:12:10
    编辑于：2022-02-20 11:12:13
    浏览量：890

概述

https://leetcode.com/problems/house-robber-iii/

动态规划法

class Solution {
public:
    unordered_map<TreeNode*, int> dp;
    int rob(TreeNode* root) {
        if (!root) return 0;
        if (dp.count(root) != 0) return dp[root];
        int notRobRoot = rob(root->left) + rob(root->right);  // don't rob root
        int robRoot = root->val;
        if (root->left) robRoot += rob(root->left->left) + rob(root->left->right);
        if (root->right) robRoot += rob(root->right->left) + rob(root->right->right);
        dp[root] = max(notRobRoot, robRoot);
        return dp[root];
    }
};

Links: leetcode-337-house-robber-iii