打家劫舍 II
House Robber II
本机进度仅保存在当前浏览器
题目描述
这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。给定一个代表每个房屋存放金额的非负整数数组，计算在不触动警报装置的情况下，今晚能够偷窃到的最高金额。
示例：nums = [2, 3, 2]，输出 3（首尾不能同时偷，只能偷 3）。
解题思路
- 环形约束的本质：首尾两间不能同时偷。拆成两个线性子问题即可。
- 子问题一：偷 [0, n-2]（不含尾）；子问题二：偷 [1, n-1]（不含首），各自用第 198 题解法。
- 答案取两子问题较大值；单间房屋与空输入要单独处理。
参考实现
查看参考实现Python · 建议先自行作答
def rob(nums):
def rob_line(houses):
prev = cur = 0
for x in houses:
prev, cur = cur, max(cur, prev + x)
return cur
if len(nums) == 1:
return nums[0]
# 首尾不相容，拆成两条线性链取较大
return max(rob_line(nums[:-1]), rob_line(nums[1:]))