213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

其实就是把环拆成两个队列，一个是从0到n-1，另一个是从1到n，然后返回两个结果最大的。

  1. //自顶向下，
  2. func rob(nums []int) int {
  3.     if len(nums) == 0 {
  4.         return 0
  5.     }
  6.     if len(nums) == 1 {
  7.         return nums[0]
  8.     }
  10.     n := len(nums)
  12.     dp_1:=make([]int, n)
  13.     dp_1[0]=nums[0]
  14.     dp_1[1]=max(nums[0],nums[1])
  17.     for i := 2;i < n;i++{
  18.         dp_1[i] = max(dp_1[i-2] + nums[i], dp_1[i-1])           //考虑本次打劫+权重，和上次是否打劫
  19.     }
  21.     dp_2:=make([]int,len(nums))
  22.     dp_2[0]=0
  23.     dp_2[1]=nums[1]
  26.     for i := 2; i < n; i++{
  27.         dp_2[i] = max(dp_2[i-2]+nums[i], dp_2[i-1])             //考虑本次打劫+权重，和上次是否打劫
  28.     }
  30.     return max(dp_1[n-2], dp_2[n-1])                //核心在这里：n-2正常打劫；n-1强制第一次不打
  31. }
  33. func max(x, y int) int {
  34.     if x > y {
  35.         return x
  36.     }
  37.     return y
  38. }
//滚动数组 记忆化
func _rob(nums []int) int {
    first, second := nums[0], max(nums[0], nums[1])

    for _, v := range nums[2:] {
        first, second = second, max(first +v, second)        // v == num[i]
    }
    return second
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    if n == 2 {
        return max(nums[0], nums[1])
    }
    return max(_rob(nums[:n-1]), _rob(nums[1:]))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}