LeetCode 【198. 打家劫舍】要是看不懂，我就去出家

写在前面：

不要单纯为了做题而做题！培养思维，举一反三很重要！

今天通过一道非常经典的 LeetCode 题《打家劫舍》，来和大家一步步的，重温 动态规划 的基本套路和该类题的思路。关注我，后续将会有《213. House Robber II》、《House Robber III》的题解分析。

欢迎大佬关注在下的微信公众号“张氏文画”，不光有新鲜的 LeetCode 题解（多种思路，包教包会，开拓思维），还有经典的文章及短视频和大家分享，一起嘿嘿嘿
图片说明

题目描述：

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

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

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

难度等级：

Easy

测试样例：

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), 
rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12

思路一：

其实，思考题意，可以发现，合格的小偷永远不会连续放过3个房屋而不偷点东西。

为什么呢？因为合格的小偷总是可以选择偷盗中间的房屋。

哈哈，接下来进入正题：我们一步步来还原经典的动态规划思路

第 1 步：定义状态

dp[i]：区间 [0，i] 里可偷得的最大金额。

第 2 步：定义状态转移方程

可以看到，我们没有限定是否偷盗下标为 i 的这个房屋，因此需要分情况：

偷盗当前房屋，那么就一定不会偷盗上一间相邻的房屋，由于状态 dp[i - 1] 的定义涵盖了偷盗下标为 i - 1 这一间房屋的情况，因此状态只能从下标为 i - 2 的状态转移而来，即：dp[i - 2] + nums[i];
不偷盗当前房屋，那么上一间相邻的房屋可以选择偷，也可以不偷，状态从下标为 i - 1 的状态转移而来：dp[i - 1]；
二者取最大值，因此最终的状态转移方程为：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

第 3 步：定义相关初始化

观察我们的状态转移方程，下标最小到 i - 2，因此初始化的时候要把 dp[0] 和 dp[1] 表示出来，从 dp[2] 开始计算。

dp[0]：只有 1 间房屋的时候，作为一名合格的小偷，必须得偷啊，不能空手而归啊，因此 dp[0] = nums[0]；
dp[1]：当有多于一间房屋的时候，对于前两间，由于不能都偷窃，会触发警告，因此最优值是这两间房屋里现金数量的最大值，即 dp[1] = max(nums[0], nums[1])；

第 4 步：定义输出

鉴于我们定义的状态有前缀性质，并且对于下标为 i 的这间房屋也考虑了被偷与不被偷的情况，因此输出就是最后一间房屋的状态值。

第 5 步：是否可以状态压缩（见思路二）

其实，观察我们自定义的状态转移方程。当前状态只与前两个状态相关，而我们只关心最后一间房屋的状态值，因此可以使用 「滚动变量」 的技巧，不过，这样的代码就丢失了可读性。

代码：

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

class Solution {
    public int rob(int[] nums) {
        // 边界情况处理，养成良好的编码习惯
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

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

        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[len - 1];
    }
}

Result：

Runtime：0ms

Your runtime beats 100% of java submissions.

思路二：

接思路一的第五步：是否可以状态压缩，从而能够在O(n)时间复杂度和O(1)额外空间复杂度内解答该题。

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

代码：

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

class Solution {
    public int rob(int[] nums) {
        // 边界情况处理，养成良好的编码习惯
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        int premax = 0, prepremax = 0;
        for (int i = 0; i < len; i++) {
            int max = Math.max(premax, prepremax + nums[i]);
            prepremax = premax;
            premax = max;
        }

        return premax;
    }
}

Result：

Runtime：0ms

Your runtime beats 100% of java submissions.

大佬们，记得随手关注下我的公众号哦！，一起嘿嘿嘿
图片说明

------至所有正在努力奋斗的程序猿们！加油！！
有码走遍天下 ***寸步难行
1024 - 梦想，永不止步!
爱编程不爱Bug
爱加班不爱黑眼圈
固执但不偏执
疯狂但不疯癫
生活里的菜鸟
工作中的大神
身怀宝藏，一心憧憬星辰大海
追求极致，目标始于高山之巅
一群怀揣好奇，梦想改变世界的孩子
一群追日逐浪，正在改变世界的极客
你们用最美的语言，诠释着科技的力量
你们用极速的创新，引领着时代的变迁

——乐于分享，共同进步，欢迎留言讨论
——Treat Warnings As Errors
——Any comments greatly appreciated
——Talking is cheap, show me the code
——微信公众号：张氏文画