Day47 (Golang) 动态规划 198.打家劫舍 213.打家劫舍II 1337.打家劫舍 III

func rob(nums []int) int {
	switch len(nums) { //判断数组元素是否为0和1
	case 0:
		return 0
	case 1:
		return nums[0]
	}
	// dp数组的含义：考虑下标i（包含）所偷的最大的金币数
	dp := make([]int, len(nums))
	//dp初始化
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	//遍历顺序为从左到右
	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-2]+nums[i], dp[i-1]) //分为偷i和不偷i两种情况
	}
	return dp[len(nums)-1]
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func rob(nums []int) int {
	if len(nums) <= 1 {
		return robWithoutCircle(nums)
	}
	res1 := robWithoutCircle(nums[:len(nums)-1]) //去除最后一个元素
	res2 := robWithoutCircle(nums[1:])           //去除第一个元素
	return max(res1, res2)
}

// 打家劫舍I代码
func robWithoutCircle(nums []int) int {
	switch len(nums) {//判断数组元素是否为0和1
	case 0:
		return 0
	case 1:
		return nums[0]
	}
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-2]+nums[i], dp[i-1])
	}
	return dp[len(nums)-1]
}

/**
 * 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}
	}
	//遍历二叉树的顺序为后序遍历：左右中 dp数组只有两个元素，dp[0]表示不偷该节点的最大金钱数，dp[1]表示偷该节点的最大金钱数
	left := robTree(cur.Left)
	right := robTree(cur.Right)
	norobCur := max(left[0], left[1]) + max(right[0], right[1]) //不偷该节点，偷他的左右孩子
    robCur := cur.Val + left[0] + right[0]                      //偷该节点，不偷他的左右孩子
    return []int{norobCur,robCur}//注意顺序
}