1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// @Title: 打家劫舍 II (House Robber II)
// @Author: 15816537946@163.com
// @Date: 2021-04-16 23:01:05
// @Runtime: 0 ms
// @Memory: 2 MB

func _rob(nums []int) int {
	// first 对于偶数位上的最大值的记录
	// second 对于奇数位上的最大值的记录
	first, second := nums[0], max(nums[0], nums[1])
	for _, v := range nums[2:] {
		first, second = second, max(first+v, second)
	}
	return second
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func rob(nums []int) int {
	n := len(nums)
	if n == 1 {
		return nums[0]
	}
	if n == 2 {
		return max(nums[0], nums[1])
	}
	// 把环斩断，就变成了 198 题
	// 斩断的方式分为，在 0 位和不在 0 位 两种。
	return max(_rob(nums[:n-1]), _rob(nums[1:]))

}