198 打家劫舍

2026年5月2日

一、题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

二、题解

思路

这道题不能简单地使用贪心算法（比如只挑最大的偷，或者隔一个偷一个），因为局部最优并不一定能带来全局最优。需要用动态规划的思想来统筹全局。

1. 定义状态 假设数组的长度为 $n$ 。我们定义一个数组 dp，其中 dp[i] 表示前 $i$ 间房屋能偷窃到的最高总金额。

2. 状态转移方程 对于第 $i$ 间房屋（下标从 0 开始），小偷只有两种选择：

偷第 $i$ 间房屋： 那么他就不能偷第 $i-1$ 间房屋，所以此时的最大金额是前 $i-2$ 间房屋的最高总金额加上当前房屋的金额，即 dp[i-2] + nums[i]。
不偷第 $i$ 间房屋： 那么他就可以安全地保留前 $i-1$ 间房屋的最高总金额，即 dp[i-1]。

为了获得最大收益，小偷会在“偷”与“不偷”之间选择金额较大的那个方案。所以状态转移方程为： $dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$

3. 初始化（边界条件）

如果没有房屋（数组为空），能偷到的金额是 0。
如果只有 1 间房屋，只能偷这间，dp[0] = nums[0]。
如果有 2 间房屋，只能选金额较大的一间偷，dp[1] = \max(nums[0], nums[1])。

4. 空间优化

注意到状态转移方程中，dp[i] 只和它前面的两个状态 dp[i-1] 和 dp[i-2] 有关。因此，我们不需要开辟一个完整的 dp 数组，只需要维护两个变量来记录前两个状态即可，这样可以将空间复杂度从 $O(n)$ 降到 $O(1)$ 。

class Solution {
    public int rob(int[] nums) {
        // 边界条件处理
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        // prevMax 代表 dp[i-2]，初始值为前 1 间房的最大收益
        int prevMax = nums[0];
        // currMax 代表 dp[i-1]，初始值为前 2 间房的最大收益
        int currMax = Math.max(nums[0], nums[1]);

        // 从第 3 间房（下标为 2）开始遍历
        for (int i = 2; i < nums.length; i++) {
            // 暂存当前的 currMax，因为它在下一步会变成新的 prevMax
            int temp = currMax;

            // 根据状态转移方程更新当前的最高金额
            // 选择不偷当前房屋（保持 currMax）还是偷当前房屋（prevMax + nums[i]）
            currMax = Math.max(currMax, prevMax + nums[i]);

            // 将原来的 currMax 赋值给 prevMax，为下一次循环做准备
            prevMax = temp;
        }

        return currMax;
    }
}

时间复杂度： $O(n)$

空间复杂度： $O(1)$

一、题目

二、题解

思路

评论