003.打家劫舍

• 198.打家劫舍
  • 思路 1
  • 思路 2
• 213.打家劫舍 II
• 337.打家劫舍 III
  • 树形 dp

打家劫舍 - 思路 1 §

func rob(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	dp := [2]int{
		nums[0], // 偷
		0, // 不偷
	}
	for i := 1; i < n; i++ {
		dp = [2]int{
			dp[1] + nums[i], // 偷
			max(dp[0], dp[1]), // 不偷
		}
	}
 
	return max(dp[0], dp[1])
}

打家劫舍 - 思路 2 §

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

打家劫舍 II §

对于一个数组，成环的话主要有如下三种情况：

1. 考虑不包含首尾元素
2. 考虑包含首元素，不包含尾元素
3. 考虑包含尾元素，不包含首元素

而 2 和 3 都包含了 1 了，所以只考虑 2 和 3 就可以了

func rob(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}
 
	res1 := process(nums[1:])
	res2 := process(nums[:n - 1])
 
	return max(res1, res2)
}
 
func process(nums []int) int {
	n := len(nums)
	dp0 := nums[0]
	if n == 1 {
		return dp0
	}
	dp1 := max(nums[0], nums[1])
	for i := 2; i < n; i++ {
		dp0, dp1 = dp1, max(dp0 + nums[i], dp1)
	}
	return dp1
}

打家劫舍 III §

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
	res := process(root)
	return max(res[0], res[1])
}
 
/*
	@return
		0: 偷
		1: 不偷
*/
func process(root *TreeNode) [2]int {
	if root == nil {
		return [2]int{ 0, 0 }
	}
	left := process(root.Left)
	right := process(root.Right)
 
	// 偷 root
	val1 := root.Val + left[1] + right[1]
	// 不偷 root
	val2 := max(left[0], left[1]) + max(right[0], right[1])
 
	return [2]int{ val1, val2 }
}