题目描述

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

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

算法1

(状态机dp) $O(n)$

本题为环形版本打家劫舍，正常来说碰到环形问题，都可以将原数组复值添加到自身后面，然后做一遍处理，取头分别为1到n的答案的最值。但本题并非如此，考察题目特点，对于头结点，最终的答案一定是max(偷了头结点，没偷头结点)，所以其实只要对这两种情况求出相应的最高金额即可，还要注意，对于偷了头结点的情况，尾结点不能偷，用f[i][0]表示i结点没偷的最高金额，f[i][1]表示偷了的，所以我们最后返回的就是f[n][0]，而没偷头结点的情况，等价于忽略原结点，从下一个结点开始走，最终取最大值是f[n][1]，然后两种情况的最值就是结果。

时间复杂度

参考文献

Golang 代码

func rob(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    } else if n == 1 {
        return nums[0]
    } else if n == 2 {
        return max(nums[1], nums[0])
    }
    f := make([][2]int, n)
    f[0][1] = nums[0]
    for i := 1; i < n; i++ {
        f[i][0] = max(f[i-1][0], f[i-1][1])
        f[i][1] = f[i-1][0] + nums[i]
    }
    res := f[n-1][0]
    f[1][0], f[1][1] = 0, nums[1]
    for i := 2; i < n; i++ {
        f[i][0] = max(f[i-1][0], f[i-1][1])
        f[i][1] = f[i-1][0] + nums[i]
    }
    res = max(res, f[n-1][1])
    return res
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla