Golang:
思路：这题我个人感觉要复杂一些，难度在于首尾相连，并且，你需要考虑的更全面一些。当然，这题做完的时间复杂度100%，空间47%，但我不太想优化了。简单来说，有房子[1...n]，通过打家劫舍1得出的最大值，我们需要做出判断：如果我们没抢n，那么这个最大值没有问题，如果我们抢了n，那么就需要去看下我们抢没抢1，如果也没抢1，那么没问题，但如果抢1了，那么这个最大值就需要修改了，为max([2....n],[1...n-1])。
代码如下：
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
if len(nums) == 2 {
if nums[0] > nums[1] {
return nums[0]
} else {
return nums[1]
}
}
res := make([]int, len(nums))
res[0] = nums[0]
if nums[0] > nums[1] {
res[1] = nums[0]
} else {
res[1] = nums[1]
}
arr := make([]int, len(nums))
arr[1]=nums[1]
i := 2
for i < len(res) {
if nums[i]+res[i-2] > res[i-1] {
res[i] = nums[i] + res[i-2]
} else {
res[i] = res[i-1]
}
if nums[i]+arr[i-2] > arr[i-1] {
arr[i] = nums[i] + arr[i-2]
} else{
arr[i] = arr[i-1]
}
i++
}
if res[i-1]==res[i-2] {//最末尾的房子没动
return res[i-1]
}else{
if res[i-1]==arr[i-1]{//最开始的房子没动
return res[i-1]
}else {
if res[i-2]>arr[i-1] {
return res[i-2]
}else {
return arr[i-1]
}
}
}
}
有疑问加站长微信联系（非本文作者）
