动态规划part9 | ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

---

198.打家劫舍

198.打家劫舍

思路

dp含义，偷前i个房，切第i个房偷
dp[i]=max(dp[i-2],dp[i-3])+nums[i]
所以结果为
max(dp[len(nums)-1],dp[len(nums)-2])

思路代码

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

官方题解

确定dp数组（dp table）以及下标的含义
dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

确定递推公式
决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

代码

func rob(nums []int) int {n := len(nums)dp := make([]int, n+1) // dp[i]表示偷到第i家能够偷得的最大金额dp[1] = nums[0]for i := 2; i <= n; i++ {dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])}return dp[n]
}func max(a, b int) int {if a > b {return a}return b
}

---

213.打家劫舍II

213.打家劫舍II

思路

成环收尾不能相连，所以分两种情况，第一种去掉头，第二种去掉尾，然后分别计算dp即可，最后取最大值即可。

思路代码

func rob(nums []int) int {if len(nums)==1{return nums[0]}if len(nums)==2{return max(nums[0],nums[1])}dp1:=make([]int,len(nums)-1)dp2:=make([]int,len(nums)-1)dp1[0]=nums[0]dp1[1]=max(nums[0],nums[1])dp2[0]=nums[1]dp2[1]=max(nums[1],nums[2])for i:=2;i<len(nums)-1;i++{dp1[i]=max(nums[i]+dp1[i-2],dp1[i-1])dp2[i]=max(nums[i+1]+dp2[i-2],dp2[i-1])}return max(dp1[len(nums)-2],dp2[len(nums)-2])
}func max(i,j int)int{if i<j{return j}return i
}

官方代码

func rob(nums []int) int {if len(nums) == 1 {return nums[0]}if len(nums) == 2 {return max(nums[0], nums[1])}result1 := robRange(nums, 0)result2 := robRange(nums, 1)return max(result1, result2)
}// 偷盗指定的范围
func robRange(nums []int, start int) int {dp := make([]int, len(nums))dp[1] = nums[start]for i := 2; i < len(nums); i++ {dp[i] = max(dp[i - 2] + nums[i - 1 + start], dp[i - 1])}return dp[len(nums) - 1]
}func max(a, b int) int {if a > b {return a}return b
}

困难

去掉头和去掉尾

---

337.打家劫舍III

思路

后序遍历
树形dp，返回当前偷还是不偷的情况

思路代码

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func rob(root *TreeNode) int {return max(dfs(root)[0],dfs(root)[1])
}func dfs(node *TreeNode) []int{if node==nil{return []int{0,0}}left:=dfs(node.Left)right:=dfs(node.Right)robthis:=node.Val+left[1]+right[1]notrobthis:=max(left[0],left[1])+max(right[0],right[1])return []int{robthis,notrobthis}
}func max(i,j int)int{if i<j{return j}return i
}

官方题解

这道题目算是树形dp的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。

确定递归函数的参数和返回值
这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

参数为当前节点，代码如下：

vector robTree(TreeNode* cur) {
其实这里的返回数组就是dp数组。

所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

所以本题dp数组就是一个长度为2的数组！

那么有同学可能疑惑，长度为2的数组怎么标记树中每个节点的状态呢？

别忘了在递归的过程中，系统栈会保存每一层递归的参数。

如果还不理解的话，就接着往下看，看到代码就理解了哈。

代码

func rob(root *TreeNode) int {res := robTree(root)return max(res[0], res[1])
}func max(a, b int) int {if a > b {return a}return b
}func robTree(cur *TreeNode) []int {if cur == nil {return []int{0, 0}}// 后序遍历left := robTree(cur.Left)right := robTree(cur.Right)// 考虑去偷当前的屋子robCur := cur.Val + left[0] + right[0]// 考虑不去偷当前的屋子notRobCur := max(left[0], left[1]) + max(right[0], right[1])// 注意顺序：0:不偷，1:去偷return []int{notRobCur, robCur}
}

困难

树形dp，长度只需为2，别忘了在递归的过程中，系统栈会保存每一层递归的参数。

---

今日收获

打家劫舍问题，重点是当前位置偷还是不偷，然后判断哪种更大。

树形dp，长度只需为2，别忘了在递归的过程中，系统栈会保存每一层递归的参数。
这道题是树形DP的入门题目，通过这道题目大家应该也了解了，所谓树形DP就是在树上进行递归公式的推导。

所以树形DP也没有那么神秘！

只不过平时我们习惯了在一维数组或者二维数组上推导公式，一下子换成了树，就需要对树的遍历方式足够了解！