打家劫舍

根据房子价值存储的数据结构有三种题型：数组、环和二叉树，设抢劫的房子不能相邻，求此种条件下抢劫的房子的最大总价值

数组：设dp数组，前i个房子的最大价值为dp[i]，则前i+2个房子的最大价值是max(dp[i]+nums[i+2], dp[i+1])，dp[n-1]即为解。

环：设数组的打家劫舍的解是hra(nums[:])，则该问题下的解是max(hra(nums[:-1]), hra(nums[1:]))

二叉树：

pair<int, int> findLargest(TreeNode* root){
	if(!root)return {0, 0};
	pair<int, int> l = findLargest(root->left);
	pair<int, int> r = findLargest(root->right);
	return {max(root->val+l.second+r.second, l.first+r.first), l.first+r.first};
}
int houseRobber3(TreeNode* root){
	return findLargest(root).first;
}

后序遍历，递归首先返回叶子节点及其孙子节点（象征性地为0）的和与子节点的和，findLargest返回值第一个参数指当前子树的最大价值，递归返回的第二层变为子节点的最大价值，第二个参数指两个子节点的最大价值之和，递归返回的第二层变为某一分支孙子节点的最大价值之和。比如说四层的满二叉树，根节点、根节点的左子树的第二层、根节点的右子树的第三层被选为打家劫舍的对象的情况是存在的。我解题时错误判定满足题解的会是一层一层地黑白相间的树，机械地转成数组来做，过不去。

创建于2022.3.10/14.24，修改与2022.3.10/14.24

#dp