动态规划简单2 种解法
#198打家劫舍
在线性房屋中选择互不相邻的房屋，使偷窃金额总和最大。
#数组#动态规划
原题
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
解题主线
- 处理到第 i 间房时，只需比较不偷它的 dp[i-1] 与偷它的 dp[i-2]+nums[i]。
解法 1：动态规划数组
dp[i] 表示前 i 间房可获得的最大金额。
-
时间复杂度： O(n)
-
空间复杂度： O(n)
final class Solution {
public int rob(int[] nums) {
int[] dp = new int[nums.length + 1];
if (nums.length == 0) return 0;
// dp[houses] 表示前 houses 间房可取得的最大金额
dp[1] = nums[0];
for (int houses = 2; houses <= nums.length; houses++) {
// 当前房只能在“不偷”与“偷且跳过前一房”之间取优
dp[houses] = Math.max(dp[houses - 1], dp[houses - 2] + nums[houses - 1]);
}
return dp[nums.length];
}
}解法 2：滚动状态
递推只依赖前两项，用 previous 与 current 压缩 dp 数组。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
final class Solution {
public int rob(int[] nums) {
int previous = 0;
int current = 0;
for (int money : nums) {
// previous、current 分别对应处理当前房前的 dp[i-2]、dp[i-1]
int next = Math.max(current, previous + money);
// 必须同步滚动旧状态，避免覆盖下一轮仍需使用的 dp[i-2]
previous = current;
current = next;
}
return current;
}
}边界与易错点
- 空数组应返回 0。
- 滚动变量更新前要保存新状态，不能覆盖仍需使用的 dp[i-2]。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q198_dp_rob.java