213. 打家劫舍Ⅱ

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

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

示例1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

解题

因为第一个和最后一个不能同时偷,所以这里提供一种方法,就是我们人为的把第一个或最后一个去掉,这样就第一或最后一个就不会同时选中。


func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	if len(nums) == 1 {
		return nums[0]
	}

	n := len(nums)
	f1 := make([]int, n)
	f1[0] = 0
	f1[1] = nums[0]

	f2 := make([]int, n)
	f2[0] = 0
	f2[1] = nums[1]

	// 从第一个开始偷,不偷最后一个,nums小标从1开始算
	for i := 2; i < n; i++ {
		if f1[i-1] < f1[i-2]+nums[i-1] {
			f1[i] = f1[i-2] + nums[i-1]
		} else {
			f1[i] = f1[i-1]
		}
	}

	// 从第一个开始偷,不偷第一个,nums从小标2开始算
	for i := 2; i < n; i++ {
		if f2[i-1] < f2[i-2]+nums[i] {
			f2[i] = f2[i-2] + nums[i]
		} else {
			f2[i] = f2[i-1]
		}
	}

	if f1[n-1] > f2[n-1] {
		return f1[n-1]
	} else {
		return f2[n-1]
	}
}