动态规划简单2 种解法

#198打家劫舍

在线性房屋中选择互不相邻的房屋，使偷窃金额总和最大。

#数组#动态规划

解题主线

处理到第 i 间房时，只需比较不偷它的 dp[i-1] 与偷它的 dp[i-2]+nums[i]。

解法 1：动态规划数组

dp[i] 表示前 i 间房可获得的最大金额。

时间复杂度

O(n)

空间复杂度

O(n)

198. 打家劫舍 · 动态规划数组

java

final class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 1];
        if (nums.length == 0) return 0;
        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];
    }
}

dp[i] 表示前 i 间房可获得的最大金额。

解法 2：滚动状态

递推只依赖前两项，用 previous 与 current 压缩 dp 数组。

时间复杂度

O(n)

空间复杂度

O(1)

198. 打家劫舍 · 滚动状态

java

final class Solution {
    public int rob(int[] nums) {
        int previous = 0;
        int current = 0;
        for (int money : nums) {
            int next = Math.max(current, previous + money);
            previous = current;
            current = next;
        }
        return current;
    }
}

递推只依赖前两项，用 previous 与 current 压缩 dp 数组。

边界与易错点

空数组应返回 0。
滚动变量更新前要保存新状态，不能覆盖仍需使用的 dp[i-2]。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

medium/Q198_dp_rob.java