从下面代码中的这一段
a0 := nums[0]
a1 := nums[1]
a2 := a0+nums[2]
复制代码
可知,从索引3开始,偷房屋i后的最高金额是由“a0和a1的最大值”以及房屋i中的金额相加得到。因为a2包含了a0,同时a0、a1、a2是迭代更新的,所以每个房屋i只需要考虑a0和a1。以下代码是从一维dp数组的基础上简化而成的,如果不容易理解,请读者先写一遍基于一维dp数组的实现。
func rob(nums []int) int {
l := len(nums)
if l == 0 {
return 0
}
if l == 1 {
return nums[0]
}
if l == 2 {
return max(nums[0], nums[1])
}
// l > 2
a0 := nums[0]
a1 := nums[1]
a2 := a0+nums[2]
for i := 3; i < l; i++ {
// 不能偷相邻的房屋
temp := nums[i] + max(a0,a1)
a0 = a1
a1 = a2
a2 = temp
}
return max(a1,a2)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复制代码
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END