House Robber II

题目描述

打家劫舍2

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例：

输入：nums = [1,2,3,4]
输出：4

解法

解法一：回溯法

复杂度较高，不做讨论。

解法二：动态规划

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    m1 := myrob(nums[0 : len(nums)-1])
    m2 := myrob(nums[1:])

    if m1 > m2 {
        return m1
    }
    return m2
}

func myrob(nums []int) int {
    pre, cur := 0, 0
    for i := 0; i < len(nums); i++ {
        tmp := cur
        if cur < pre+nums[i] {
            cur = pre + nums[i]
        }
        pre = tmp
    }
    return cur
}