本文主要是介绍Leetcode 337 打家劫舍三 (树形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// 经典树形dp
// dp[i][0] 表示不抢i节点
// dp[i][1] 表示抢i节点
// dp[i][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1]);
// dp[i][1] = nums[i] + dp[left][0] + dp[right][0];
// 很好理解吧class Solution {
public:unordered_map<TreeNode*, int> mp[2];int rob(TreeNode* root) {int no = dp(root, 0);int yes = dp(root, 1);return std::max(no, yes);}int dp(TreeNode* root, int flag) {if (root == nullptr)return 0;if (mp[flag].find(root) != mp[flag].end())return mp[flag][root];if (flag == 1) {mp[flag][root] = root->val + dp(root->left, 0)+ dp(root->right, 0);}else {int leftYes = dp(root->left, 1);int leftNo = dp(root->left, 0);int rightYes = dp(root->right, 1);int rightNo = dp(root->right, 0);mp[flag][root] = std::max(leftYes, leftNo) + std::max(rightYes, rightNo);}return mp[flag][root];}
};这篇关于Leetcode 337 打家劫舍三 (树形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
