198. 打家劫舍#

class Solution {
    // 方法一：基础动态规划解法
    public int rob(int[] nums) {
        // 边界情况：没有房子可偷，收益为 0
        if (nums == null || nums.length == 0) return 0;
        // 边界情况：只有一间房子，只能偷它
        if (nums.length == 1) return nums[0];

        // dp[i] 表示偷到第i间房子时能得到的最大金额
        int[] dp = new int[nums.length];

        // 初始化第 0 间房：只能选择偷第 0 间
        dp[0] = nums[0];
        // 初始化第 1 间房：在第 0 间和第 1 间中选金额更大的
        dp[1] = Math.max(nums[0], nums[1]);

        // 从第 2 间房开始进行状态转移
        for (int i = 2; i < nums.length; i++) {
            // 两种选择取最大值：
            // 1) 不偷当前房子：收益为 dp[i-1]
            // 2) 偷当前房子：收益为 dp[i-2] + nums[i]
            dp[i] = Math.max(dp[i-1],         // 不偷当前房子
                            dp[i-2] + nums[i]  // 偷当前房子
                           );
        }

        // 最后一个状态就是偷完整条街后的最大收益
        return dp[nums.length - 1];
    }

    // 方法二：空间优化版本
    public int robOptimized(int[] nums) {
        // 边界情况：空数组时无收益
        if (nums == null || nums.length == 0) return 0;
        // 边界情况：只有一间房时，直接返回该房金额
        if (nums.length == 1) return nums[0];

        // 由于 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，用滚动变量优化空间
        int prev2 = nums[0];                    // prev2 表示 dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]); // prev1 表示 dp[i-1]
        int current = prev1;                    // current 表示当前计算的 dp[i]

        for (int i = 2; i < nums.length; i++) {
            // 计算当前最优值：偷或不偷当前房子，取最大收益
            current = Math.max(prev1, prev2 + nums[i]);
            // 状态前移：旧的 dp[i-1] 变成下一轮的 dp[i-2]
            prev2 = prev1;
            // 状态前移：当前 dp[i] 变成下一轮的 dp[i-1]
            prev1 = current;
        }

        // 循环结束后，current 为最终最大收益
        return current;
    }
}