LeetCode.198.House Robber 打家劫舍

题目描述

198 House Robber
https://leetcode-cn.com/problems/house-robber/

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

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

示例 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 。

---

相似题目

LeetCode.198.House Robber 打家劫舍
LeetCode.程序员面试金典.1716.Masseuse 按摩师

---

解题过程

之前做过 《程序员面试金典（第 6 版）》 的 17.16 按摩师，对这个题印象还是很深刻的。

dp[i] 表示抢劫 nums[0...i] 能获得的最大收益，则对于第 i 家有两个选择，选他或不选他：
选择 i 就不能选 i-1, 最大收益为 dp[i-2] + nums[i]
不选 i 就可以选 i-1，最大收益为 dp[i-1]
找出两者中的最大值作为第 i 家的选择。
所以有递推公式 dp[i] = max(dp[i-2] + nums[i], dp[i-1])

从头到尾遍历数组 nums 并填表 dp，最后 dp[nums.length - 1] 就是最终结果。

优化：由于每次的选择只依赖于 dp[i-2] 和 dp[i-1]，我们只需要两个变量记住这两个值即可，可以将空间复杂度降到 O(1)

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV202005 {
    public int rob(int[] nums) {
        // 特殊处理数组长度小于 3 的情况
        if (null == nums || nums.length < 1) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        // dp[i] 表示抢劫 nums[0...i] 能获得的最大收益，则 dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_198_HouseRobber.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_198_HouseRobber.java

---