LeetCode_129_HouseRobber

1. question: 打家劫舍（中等）

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/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 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

2. answers

这道题最开始想用背包问题解决，发现绕进去了。其实没必要，参考了题解。在以本元素X为结尾的房屋序列所能形成的最大值仅取决于【以X-1结尾的最大值，以X-2结尾的最大值+本元素】

正序看一下：

1. 只有元素【0】时，显然最大值就是【0】
2. 当有元素【0,1】时，显然最大值就是max(0,1)
3. 当有元素【0,1,2】时，显然是max(1, 0+2)
4. 当有元素【0,1,2,3】时，显然max(2, 1+3)

因此，定义数组dp[i]，保存以当前元素结尾的所有元素形成的最大值。代码如下所示：

public class Solution_0129_02 {

    public int rob(int[] nums) {

        // 判断特殊条件
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        // 定义数组，在当前元素及其前面元素形成的房屋序列中，所能形成的最大值。
        int[] dp = new int[nums.length];

        // 初始化，以第0个房屋结尾形成的序列最大值。以第1个房屋形成的序列最大值，
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);

        // 动态规划。
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[nums.length - 1];
    }
}

因为我们在计算当前元素时，仅用到了前两个元素，因此，可直接用两个空间来保存，减少空间开销。

public class Solution_0129_03 {

    public int rob(int[] nums) {

        if(nums.length == 1) return nums[0];

        // 定义数组，保存当前元素的前面两个元素形成的序列的最大值。
        int[] dp = new int[2];

        // 初始化
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);

        int temp;

        for (int i = 2; i < nums.length; i++) {

            if(dp[0] + nums[i] > dp[1]) {

                temp = dp[1];
                dp[1] = dp[0] + nums[i];
                dp[0] = temp;

            } else {
                dp[0] = dp[1];
                // dp[1]保持不变即可。
            }
        }

        return dp[1];
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0129_03 s = new Solution_0129_03();

        int[] nums = {1, 2, 3, 1};

        System.out.println(s.rob(nums));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。