计划偷窃沿街的房屋是小偷的计划。在这个地方，所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。但是，相邻的房屋都装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
为了计算在不触动警报装置的情况下，今晚能够偷窃到的最高金额，我们给定了一个代表每个房屋存放金额的非负整数数组。
示例：
- 输入：nums = [2,3,2]
- 输出：3
- 解释：小偷不能先偷窃第1号房屋（金额 = 2），然后偷窃第3号房屋（金额 = 2），因为他们是相邻的。
- 输入：nums = [1,2,3,1]
- 输出：4
- 解释：小偷可以先偷窃第1号房屋（金额 = 1），然后偷窃第3号房屋（金额 = 3）。
偷窃到的最高金额为1 + 3 = 4。
- 输入：nums = [1,2,3]
- 输出：3
提示：
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
题解:
状态表示:
f[i]
-
集合: 只考虑前 i 个房屋(包含 i (0, i]), 偷盗房屋的所有方案
-
属性: 最大值
状态计算:
- 不选第 i 个房屋, -----> 状态转移方程1: f[i] = f[i - 1];
- 选第 i 个房屋, -------> 状态转移方程2: f[i] = f[i - 2] + nums[i]; (不选第 i - 1个房子 的最大值 加上 第i个房子的价值 )
两式取max
因为房屋是围成圈的, 所以分为两种情况, "选第1个房屋, 不选最后一个屋子" 和 "不选第一个房屋, 选最后一个屋子", 两种情况都按照上面状态计算一下, 然后取max就是答案
好理解, 废空间的ac代码
标签：II,nums,int,res,力扣,房屋,max,leetcode,size From： https://www.cnblogs.com/xxctx/p/18213027