LeetCode 337. 打家劫舍 III（记忆化+递归）
LeetCode 337. 打家劫舍 III（记忆化+递归）
Michael阿明
发布于 2020-07-13 15:34:42
发布于 2020-07-13 15:34:42
1. 题目
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/house-robber-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1.1 相关题目：
LeetCode 198. 打家劫舍（DP） LeetCode 213. 打家劫舍 II（DP）
2. 解题
2.1 递归
- 父节点偷，或者不偷，相应的子节点不偷，或者偷，取max
class Solution {
public:
int rob(TreeNode* root) {
return max(rob(root,0),rob(root,1));
}
int rob(TreeNode* root, bool steal)
{
if(root == NULL)
return 0;
if(steal)
return root->val+rob(root->left,0)+rob(root->right,0);
else//没有偷
return max(rob(root->left,0),rob(root->left,1))
+max(rob(root->right,0),rob(root->right,1));
}
};暴力递归，最后一个测试例子超时。
在这里插入图片描述
2.2 记忆化递归
- 上面有很多重复子问题
- 利用map存储结果（不能用哈希map，编译报错，好像是因为hash函数需要自己定义）
Line 2: Char 42: required from here
/usr/local/include/c++/8.2.0/bits/hashtable.h:195:21: error: static
assertion failed: hash function must be invocable with an argument
of key type
static_assert(__is_invocable<const _H1&, const _Key&>{},
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~class Solution {
map<pair<TreeNode*,bool>,int> m;
public:
int rob(TreeNode* root) {
return max(rob(root,0),rob(root,1));
}
int rob(TreeNode* root, bool steal)
{
if(root == NULL)
return 0;
if(m.find(make_pair(root,steal)) != m.end())
return m[make_pair(root,steal)];
if(steal)
{
int val = root->val + rob(root->left,0) + rob(root->right,0);
m[make_pair(root,steal)] = val;
return val;
}
else//没有偷root
{
int val = max(rob(root->left,0),rob(root->left,1))
+max(rob(root->right,0),rob(root->right,1));
m[make_pair(root,steal)] = val;
return val;
}
}
};
在这里插入图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-10-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录