198. 打家劫舍 | 程序之心

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // prev1 表示前一间房屋的最大金额
        // prev2 表示前前一间房屋的最大金额
        int prev1 = 0, prev2 = 0;

        // 遍历每间房屋
        for (int num : nums) {
            // 临时保存 prev1
            int temp = prev1;
            // 当前最大金额 = max(偷当前房屋+前前一间房屋的金额, 不偷当前房屋)
            prev1 = Math.max(prev2 + num, prev1);
            // 更新 prev2
            prev2 = temp;
        }

        return prev1;
    }
}

算法解析：

动态规划思路：
- 对于每间房屋，我们有两个选择：偷或不偷
- 如果偷当前房屋，就不能偷前一间房屋，总金额 = 前前一间房屋的最大金额 + 当前房屋金额
- 如果不偷当前房屋，总金额 = 前一间房屋的最大金额
- 状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
空间优化：
- 由于每次状态转移只需要前两个状态，我们用两个变量 prev1 和 prev2 代替整个dp数组
- 空间复杂度从 O(n) 优化为 O(1)
时间复杂度：O(n)，其中 n 是房屋数量
空间复杂度：O(1)，只使用了常数级额外空间

这个解法高效且简洁，能够处理所有边界情况，包括空数组和只有一个元素的数组。