主要总结了动态规划的打家劫舍问题
对应leetcode题目为198.213.337
代码地址https://github.com/Ltd5552/Algorithm/tree/master/8-DP/Rob
198.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
分析
对每一个房屋都存在偷与不偷两种情况，但为了避免触发报警，不能连续偷相邻的房屋，所以在偷之前需要依赖之前的状态，这就是一个状态转移的过程，显然也有重叠子问题，可以通过这个过程推导出递推方程，利用动态规划解决。
-
dp[i]定义为偷取下标为1-i号房屋最多可以获取的金额；
-
递推公式
- 偷第i间房：那么就一定不能偷第i-1间，所以通过dp[i-2]推出
- 不偷第i间房：那么就通过dp[i-1]推出，这里的dp[i-1]并不一定要偷第i-1间房，只是从最开始偷到第i-1间房了金额获取最大的状态（子状态）
dp[i] = Max(dp[i-1], dp[i-2]+nums[i])所以递推公式如上
-
初始化很好解释，dp[0]就肯定是nums[0]，必偷，dp[1]是选择nums[0]和nums[1]中更大的那个，而剩下的都由dp[0]和dp[1]推出，默认为0即可。
-
状态是向前依赖的，所以一定是从前往后遍历
代码
func rob(nums []int) int {
dp := make([]int, len(nums))
dp[0] = nums[0]
if len(nums) == 1 {
return dp[0]
}
dp[1] = Max(nums[0], nums[1])
for i := 2; i < len(nums); i++ {
// 当前这个不偷那么就直接是dp[i-1]，当前这个要偷只能是从dp[i-2]递推过来，选择这两个里面更大的即可
dp[i] = Max(dp[i-1], dp[i-2]+nums[i])
}
return dp[len(nums)-1]
}
213.打家劫舍II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3]
输出：3
分析
这是一个环形的房屋结构，相对上一题增加了首尾不能同时偷取的限制。
最开始想到的是对最后一个增加判断，如果第一个偷了最后一个就不能偷，但最后一个偷了第一个也不能偷，那到底是偷第一个还是偷最后一个呢，而且第一个的改变连锁影响剩下的，这就有相互制约的关系而不是简单的子问题，所以这样考虑非常麻烦。
新的思路是跳出环，将首尾偷与不偷拆分成两个子问题，一个是不考虑第一个房屋的情况下能够偷窃到的最高金额，另一个是不考虑最后一个房屋的情况下能够偷窃到的最高金额。然后，取这两个子问题的最大值作为最终的结果，这个首尾完全没关系了也就跳出了限制圈。
具体实现与上一个基本相同，只不过多了一次求dp数组的过程。
// 执行耗时:0 ms,击败了100.00% 的Go用户
// 内存消耗:1.9 MB,击败了46.81% 的Go用户
func robII(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
if len(nums) == 2 {
return Max(nums[0], nums[1])
}
//求取第1到第(n-1)个
dp1 := make([]int, len(nums))
dp1[0] = nums[0]
dp1[1] = Max(nums[0], nums[1])
for i := 2; i < len(nums)-1; i++ {
//当i是最后一个的时候选择是否
dp1[i] = Max(dp1[i-1], dp1[i-2]+nums[i])
}
//求取第2到第n个
dp2 := make([]int, len(nums))
dp2[1] = nums[1]
dp2[2] = Max(nums[1], nums[2])
for i := 3; i < len(nums); i++ {
//当i是最后一个的时候选择是否
dp2[i] = Max(dp2[i-1], dp2[i-2]+nums[i])
}
return Max(dp1[len(nums)-2], dp2[len(nums)-1])
}
337.打家劫舍III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
分析
这就又复杂不少了，主要复杂在引入了二叉树。
对于树需要想到遍历方式——前/中/后/层序
因为考虑子问题的情况，所以这一题需要用到递归函数的返回值进行下一步计算，所以是后序遍历
与前两个一样，这道题的关键还是考虑节点是否偷取：如果当前节点偷取了，子节点就不能偷；如果当前节点没有偷，那么子节点就可以偷。
动态规划
因为是树形结构，所以是基于递归的框架，使用递归函数实现。
这里使用一个长度为2的dp数组记录当前节点偷与不偷所获得的最大金额，不直接返回两者最大值是因为子节点的信息可能还有用，在当前节点的父节点偷了的情况下只能去偷取当前节点的子节点。
定义dp数组为当前节点偷或不偷所获得的最大金额
//0是不偷，1是偷
[]int{notRob, rob}
状态转移：
//偷取当前节点，意味着不能偷子节点的，所以加第0个索引的
rob := node.Val + left[0] + right[0]
//不偷取当前节点，意味着可以偷子节点，所以在子节点中选择最大的
notRob := Max(left[0], left[1]) + Max(right[0], right[1])
// 递归函数的定义：传入节点，返回的是该节点偷与不偷两种情况下所得到的金钱
func robTreeIII(root *TreeNode) int {
res := TreeII(root)
return Max(res[0], res[1])
}
func TreeII(node *TreeNode) []int {
if node == nil {
return []int{0, 0}
}
//后序遍历
left := TreeII(node.Left)
right := TreeII(node.Right)
//偷取当前节点，意味着不能偷子节点的，所以加第0个索引的
rob := node.Val + left[0] + right[0]
//不偷取当前节点，意味着可以偷子节点，所以在子节点中选择最大的
notRob := Max(left[0], left[1]) + Max(right[0], right[1])
//0是不偷，1是偷
return []int{notRob, rob}
}
更多的解法参考这里
上面这道题是一道树形dp，得更加熟悉递归和二叉树的遍历。
总结
打家劫舍是动态规划里面一类比较常见的题，感觉更多的是考察对状态转移的考虑，即找到递推关系（虽然也是整个dp主要的）。
另一点就是不同数据结构下的变通，第二题是一个环形结构的房屋如果强行用环的话会发现是闭环相扣的，所以把环拆分为两个子问题，区分开始和结束那么就是两个一般的打家劫舍问题了；对于树形结构是需要对二叉树熟练掌握，这里是一个后序遍历，利用遍历的结果合成原问题，而打家劫舍的实质还是对状态转移的确定。