建设银行泰州分行网站,1网站建设的目标是什么意思,做网站界面用什么软件,重庆八大员报名入口官网文章目录1. 题目1.1 相关题目#xff1a;2. 解题2.1 递归2.2 记忆化递归1. 题目
在上次打劫完一条街道之后和一圈房屋后#xff0c;小偷又发现了一个新的可行窃的地区。这个地区只有一个入口#xff0c;我们称之为“根”。 除了“根”之外#xff0c;每栋房子有且只有一个…
文章目录1. 题目1.1 相关题目2. 解题2.1 递归2.2 记忆化递归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. 打家劫舍 IIDP
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-valrob(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: staticassertion failed: hash function must be invocable with an argument of key typestatic_assert(__is_invocableconst _H1, const _Key{},^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~class Solution {mappairTreeNode*,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;}}
};
