2021-10-28：打家劫舍 II。你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额 。力扣213。
答案2021-10-28：
子序列不相邻最大累加和问题。
情况1：i只选。
情况2：i不选。
情况3：0~(i-2) i。
dpi取上三种情况的最大值。
0到n-2和1到n-1，根据上面的方法求出来，再取最大值，这个最大值就是需要的返回值。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
nums := []int{1, 2, 3, 4, 5}
ret := rob(nums)
fmt.Println(ret)
}
// arr 长度大于等于1
func pickMaxSum(arr []int) int {
n := len(arr)
// dp[i] : arr[0..i]范围上，随意选择，但是，任何两数不能相邻。得到的最大累加和是多少？
dp := make([]int, n)
dp[0] = arr[0]
dp[1] = getMax(arr[0], arr[1])
for i := 2; i < n; i {
p1 := arr[i]
p2 := dp[i-1]
p3 := arr[i] dp[i-2]
dp[i] = getMax(p1, getMax(p2, p3))
}
return dp[n-1]
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
if len(nums) == 2 {
return getMax(nums[0], nums[1])
}
pre2 := nums[0]
pre1 := getMax(nums[0], nums[1])
for i := 2; i < len(nums)-1; i {
tmp := getMax(pre1, nums[i] pre2)
pre2 = pre1
pre1 = tmp
}
ans1 := pre1
pre2 = nums[1]
pre1 = getMax(nums[1], nums[2])
for i := 3; i < len(nums); i {
tmp := getMax(pre1, nums[i] pre2)
pre2 = pre1
pre1 = tmp
}
ans2 := pre1
return getMax(ans1, ans2)
}执行结果如下：
在这里插入图片描述左神java代码
