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:]))
}
|