动态规划中等1 种解法
#213打家劫舍 II
房屋首尾相邻成环，选择互不相邻房屋使金额最大。
#数组#动态规划
解题主线
01
首尾不能同时选择，因此答案是区间 [0,n-2] 与 [1,n-1] 两个线性问题的较大值。
解法 1：拆环为两个线性区间
分别排除最后一间和第一间，对两个闭区间执行滚动动态规划。
时间复杂度
O(n)
空间复杂度
O(1)
java
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) {
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