LeetCode 337 House Robber III

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

概述

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];
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/