动态规划中等1 种解法
#213打家劫舍 II
房屋首尾相邻成环，选择互不相邻房屋使金额最大。
#数组#动态规划
原题
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3] 输出：3
提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000
解题主线
- 首尾不能同时选择，因此答案是区间 [0,n-2] 与 [1,n-1] 两个线性问题的较大值。
解法 1：拆环为两个线性区间
分别排除最后一间和第一间，对两个闭区间执行滚动动态规划。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
final class Solution {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
// 单间房既是首间也是末间，不能拆成两个空区间。
if (nums.length == 1) return nums[0];
// 环上首尾不能同选，分别排除末尾和开头后取较优解。
return Math.max(robLinear(nums, 0, nums.length - 2),
robLinear(nums, 1, nums.length - 1));
}
private int robLinear(int[] nums, int left, int right) {
// previous、current 分别保存前两步和前一步的区间最优值。
int previous = 0;
int current = 0;
for (int index = left; index <= right; index++) {
int next = Math.max(current, previous + nums[index]);
previous = current;
current = next;
}
return current;
}
}实现提示
- 按真实题号从 Q198_dp_robII_213.java 拆为 213，并去除旧版子数组复制。
边界与易错点
- 单间房不能拆成两个空区间，应直接返回其金额。
- 旧实现复制两个子数组产生 O(n) 额外空间，可直接传区间边界。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q198_dp_robII_213.java