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 <= 100
• 0 <= nums[i] <= 400

动态规划，递归

dp(int[] nums, int start)表示nums[start..] 能抢到的最大值，对nums[start]，有两种选择，抢和不抢，取这两种选择的最大值。

// 主函数
public int rob(int[] nums) {
    return dp(nums, 0);
}
// 返回 nums[start..] 能抢到的最大值
private int dp(int[] nums, int start) {
    if (start >= nums.length) {
        return 0;
    }

    int res = Math.max(
            // 不抢，去下家
            dp(nums, start + 1), 
            // 抢，去下下家
            nums[start] + dp(nums, start + 2)
        );
    return res;
}

时间复杂度O(2^N)，空间复杂度O(N)，递归栈空间。

动态规划-递归-备忘录

private int[] memo;
// 主函数
public int rob(int[] nums) {
    // 初始化备忘录
    memo = new int[nums.length];
    Arrays.fill(memo, -1);
    
    // 强盗从第 0 间房子开始抢劫
    return dp(nums, 0);
}

// 返回 nums[start..] 能抢到的最大值
private int dp(int[] nums, int start) {
    // 结束条件
    if (start >= nums.length) {
        return 0;
    }
    // 避免重复计算
    if (memo[start] != -1) return memo[start];

    int res = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));    
    // 记入备忘录
    memo[start] = res;
    
    return res;
}

时间复杂度O(N)

动态规划-数组递推

dp[i] 表示前 i 间房屋能够打劫到的最大金额，因为dp[i]依赖于前两个房间，所以要先计算出前两个房间的值，然后从第三个房间开始递推。注意特殊条件，例如数组为空，数组长度为0或1。正序遍历。

class Solution {
    public int rob(int[] nums) {
        // 如果输入数组为 null 或者长度为 0，返回 0
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        // 如果只有一间房屋，返回该房屋的金额
        if (length == 1) {
            return nums[0];
        }

        // 定义 dp 数组，dp[i] 表示前 i 间房屋能够打劫到的最大金额，i表示索引
        int[] dp = new int[length];
        // 初始化 dp 数组的前两项
        dp[0] = nums[0]; // 第 1 间房屋的最大金额是 nums[0]
        dp[1] = Math.max(nums[0], nums[1]); // 前两间房屋的最大金额是 nums[0] 和 nums[1] 的较大值

        // 遍历剩余的房屋，从第 3 间房屋开始
        for (int i = 2; i < length; i++) {
            // 解释：前 i 间房屋的最大金额是：
            // 1. 不打劫第 i 间房屋，最大金额是 dp[i-1]
            // 2. 打劫第 i 间房屋，最大金额是 dp[i-2] + nums[i]
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        // 返回前 length 间房屋能够打劫到的最大金额
        return dp[length - 1];
    }
}

动态规划-数组递推-滚动更新

用两个变量即可，first保存第一间房屋的金额，second保存前两间房屋的最大金额为较大值。

class Solution {
    public int rob(int[] nums) {
        // 如果输入数组为 null 或者长度为 0，返回 0
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        // 如果只有一间房屋，返回该房屋的金额
        if (length == 1) {
            return nums[0];
        }

        // 初始化前两间房屋的最大打劫金额
        int first = nums[0]; // 第一间房屋的金额
        int second = Math.max(nums[0], nums[1]); // 前两间房屋的最大金额为较大值

        // 从第三间房屋开始遍历，使用滚动数组优化空间复杂度。从左到右，先first，再second。
        for (int i = 2; i < length; i++) {
            int temp = second; // 临时保存上一轮的 second 值，因为下面要修改它
            // 计算当前房屋的最大打劫金额
            second = Math.max(first + nums[i], second);
            // 更新 first 为上一轮的 second
            first = temp;
        }

        // 返回最后计算的最大打劫金额
        return second;
    }
}

时间复杂度O(N)，空间复杂度O(1)