今日任务：

1. LeetCode198 打家劫舍
2. LeetCode213 打家劫舍 Ⅱ
3. LeetCode337 打家劫舍 Ⅲ

资料来源：

1. 代码随想录 | LeetCode198 打家劫舍
2. 代码随想录 | LeetCode213 打家劫舍 Ⅱ
3. 代码随想录 | LeetCode337 打家劫舍 Ⅲ

1 LeetCode198 打家劫舍

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

打家劫舍问题，经典dp问题。其实我写复杂了，这题对于每家来说就一个问题：抢还是不抢？dp数组记录前i家能抢的最大金额。抢的话，那就不能抢这家的前一家了，那就是这一家的钱加上这家的前两家的那个状态；不抢的话，那就直接就是这家的前一家的状态直接搬过来就行。

go
func rob(nums []int) int {
	dpArray := make([]int, len(nums) + 1)
	dpArray[1] = nums[0]
	for i := 1; i <= len(nums); i++ {
		for j := i - 2; j >= 0; j-- {
			if i - 2 < 0 {
				continue
			}
			dpArray[i] = max(dpArray[i], dpArray[j] + nums[i - 1]) // 注意dpArray是比nums多一个哪家都不抢的状态的 所以nums取值是i - 1去取值的
		}
	}
	return max(dpArray[len(nums)], dpArray[len(nums) - 1])
}

2 LeetCode213 打家劫舍 Ⅱ

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入：nums = [1,2,3]
输出：3

这题就是上一题的升级版，既然有环，切断它就是了。对于第一家和最后一家，只要不同时考虑它们俩就绝对不会出现同时抢他们两家的情况了。

go
func rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	if len(nums) == 2 {
		return max(nums[0], nums[1])
	}
	return max(dp(nums[:len(nums) - 1]), dp(nums[1:])) // 分别去掉最后一家和第一家 分别dp
}

func dp(nums []int) int {
	dpArray := make([]int, len(nums))
	dpArray[0] = nums[0]
	dpArray[1] = max(nums[0], nums[1])
	for i := 2; i <= len(nums) - 1; i++ {
		dpArray[i] = max(dpArray[i - 1], dpArray[i - 2] + nums[i])
	}
	return dpArray[len(nums) - 1]
}

3 LeetCode337 打家劫舍 Ⅲ

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

我是想到要用后序了，但是不知道后序完了之后该干什么，可惜了

这个一看就肯定是从下往上计算的，首先一个后序没跑了。对于这么一个树形结构，要推导某一节点的状态肯定是根据它的子节点来推导，那循环写法无论怎么写都没有办法来很好的记录节点之间的父子关系，因此肯定是递归。再说状态问题，对于打家劫舍问题，那状态肯定还是要么抢要么不抢：如果抢，那么抢的结果就是自身节点的值加上两个子节点不抢的值；如果不抢，那么不抢对应的肯定是两个子节点抢或者不抢的值的最大值的和（有的时候有的节点不抢比抢的结果还大，既然当前节点不抢了，那么子节点无论抢不抢其实都可以）。

go
func rob(root *TreeNode) int {
	result := recursion(root)
	return max(result[0], result[1])
}

func recursion(root *TreeNode) []int {
	if root == nil {
		return []int{0, 0}
	}
	left := recursion(root.Left)
	right := recursion(root.Right)
	
	// result是dp数组 result[0]表示抢根节点的情况 result[1]表示不抢根节点的情况
	result := make([]int, 2)
	result[0] = root.Val + left[1] + right[1] // 抢根节点的话 那两个子节点肯定是不抢的
	result[1] = max(left[0], left[1]) + max(right[0], right[1]) // 不抢根节点的话 两个子节点抢与否就要挑个大的来考虑了
	return result
}