leetcode 198. 打家劫舍

题目链接

从下面代码中的这一段

    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
喜欢就支持一下吧
点赞0 分享