前言
新的一年，好好学习
正文
问题来源
本问题来自leetcode上的213题。
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
分析：
这道题跟leetcode 198类似。
基本思路：
第一个房屋和最后一个房屋是紧挨着的，说明第一个房屋和最后一个房屋不能同时盗取。我们可以考虑两种情况：
（1）考虑偷取[0, n - 2]的房屋。
（2）考虑偷取[1, n - 1]的房屋。
取上述两种情况的大者即为答案。而对于上述两种情况，其实和LeetCode198——打家劫舍是一模一样的
func f_max(a, b int) int {
if a > b {
return a
}
return b
}
func rob(nums []int) int {
l := len(nums)
if 0 == l {
return 0
} else if 1 == l {
return nums[0]
} else if 2 == l {
return f_max(nums[0], nums[1])
}
dp1 := make([]int, l)
dp2 := make([]int, l)
dp1[0], dp1[1] = nums[0], f_max(nums[0],nums[1])
for i := 2; i < l-1; i++ {
dp1[i] = f_max(dp1[i-1], dp1[i-2]+nums[i])
}
dp2[l-2], dp2[l-1] = f_max(nums[l-2], nums[l-1]), nums[l-1]
for i := l-3; i > 0; i-- {
dp2[i] = f_max(dp2[i+1], dp2[i+2]+nums[i])
}
return f_max(dp1[l-2], dp2[1])
}
总结：
勤思考。
结语
不管怎么样好好加油。
