打家劫舍

198.打家劫舍

题意

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

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

思路一：记忆化搜索

假设你就是这个强盗，从左到右走过这一排房子，在每间房子前都有两种选择：抢或者不抢。

当你走过了最后一间房子后，你就没得抢了，能抢到的钱显然是 $0$（base case）。

以上已经明确了「状态」和「选择」：你面前房子的索引就是状态，抢和不抢就是选择。

代码：

class Solution {
    // 备忘录
    private int[] memo;

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

    // 返回 dp[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;
    }
}

思路二：递推

转化为递推，每个状态都由前面抢与不抢来决定。

当遍历到最后一间房子即 nums[n - 1] 时，推出来的状态为 f[n + 1]，所以 f[] 的长度要 $+2$，避免下标越界。

代码：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int f[] = new int[n + 2];
        for (int i = 0; i < n; i++){
            f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
        }
        return f[n + 1];
    }
}

进一步空间优化：

class Solution {
    public int rob(int[] nums) {
        int f0 = 0;
        int f1 = 0;
        for (int x : nums) {
            int newF = Math.max(f1, f0 + x);
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }
}