题目：198. 打家劫舍
思路：
决定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 {
lens := len(nums)
dp := make([]int, lens + 1)
dp[1] = nums[0]
for i:=2; i <= lens; i++ {
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
}
return dp[lens]
}
func max(a,b int) int {
if a >b {
return a
}
return b
}
参考：
题目：213. 打家劫舍 II
思路：
具体实现和上面一样，现在是环，所以第一个房间和最后一个房间最多只能拿一个，因此直接把这两部分([0,n-1] [1,n])分开计算即可，最后取较大的一个。
代码：
func rob(nums []int) int {
lens := len(nums)
if lens == 0 {
return 0
}
if lens == 1 {
return nums[0]
}
t1 := append([]int{}, nums[:lens - 1]...)
t2 := append([]int{}, nums[1:]...)
return max(run(t1, lens), run(t2, lens))
}
func run(nums []int ,lens int) int {
dp := make([]int, lens)
dp[1] = nums[0]
for i := 2; i < lens; i++ {
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
}
return dp[lens-1]
}
func max(a, b int)int {
if a > b {
return a
}
return b
}
参考：
题目：337. 打家劫舍 III
思路：
如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就再回顾一下dp数组的含义）
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
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}
}