题目

核心思路

作为典型的DP问题，主要应该分为4步：划分子问题、状态转移、自顶向下或自底向上、优化空间。我们来分步进行解题。

划分子问题

由于题目中要对n个房间进行抢劫，显而易见，抢劫一个房间即为最小子问题，对于一个独立的房间，他有两种状态：偷/不偷，只要有偷1个房间，递推到偷2、3、4......即可解决这类问题。

状态转移

这是比较重要的一步，我们可以这样想：对于第i个房间，有两种选择：

偷这个房间，那么i + 1 房间不能偷，i + 2房间可偷可不偷，故如果知道i + 2时的最大值就可以计算。
不偷这个房间，那么i + 1 房间可偷可不偷，同1所讲，使用i + 1的最大值即可。
对于这两个选择，我们要得到的是最大偷窃钱数，所以对两者选最大值即可。
根据上述思路，得到状态转移方程：

dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i];//nums为题目给定数组    dp为算法辅助数组

计算顺序

当面临选择计算顺序时，自顶向下即使用递归，自底向上即使用dp数组，通常情况下使用dp数组可以去优化空间复杂度，而且自顶向上为了提升效率须要使用额外的数组记录访问过的值，故通常选用自底向上更方便。代码如下：

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 2];//初始化最后两个位置不存在，令其为零，方便计算
        for(int i = nums.length - 1; i >= 0; i--){//自底向上
            dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i]);//状态转移
        }
        return dp[0];//最后递推到dp[0]即为最大的偷窃金额
    }
}

优化空间

根据递推公式(状态转移方程)可以发现，每次计算dp[i]的值时，只与两个值dp[i + 1], dp[i + 2]有关，故只要使用两个变量存储这两个值即可，无须使用一个完整的数组，优化如下：

class Solution {
    public int rob(int[] nums) {
        int current = 0, previous = 0;//current计算之前即代表dp[i + 1],previous代表dp[i + 2]
        for(int i = nums.length - 1; i >= 0; i--){
            int temp = current;//备份dp[i + 1]   i--后current即为 dp[i + 2]
            current = Math.max(current, previous + nums[i]);
            previous = temp;
        }
        return current;
    }
}

对于current和previous初始化为0，可以理解为额外增加的两个房间nums[nums.length + 1]和nums[nums.length + 2] 里面没有钱，不影响最大值的计算，在DP问题中，初始化也是需要思考的一个环节。

打家劫舍Ⅱ

题目如下：

与第一题相比，主要的区别即是：房间形成了一个环，即第一个房间和最后一个房间不能同时偷窃。那么主要有三种情况：第一房间偷最后一个房间不偷、第一房间不偷最后一个房间偷、两个房间都不偷。可以以不偷为标准，将三种情况合为两种：不偷第一个房间、不偷最后一个房间。至于为什么选用不偷作为标准，可以想到，如果某一个房间不偷，完全可以删掉这个房间，那么这个问题就可以变成第一题的算法中取(0 - nums.length - 2, 1 - nums.length - 1)两个值的最大值即可，所以直接用第一题的算法两次即可。即

代码如下：

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        
        int cur = 0;
        int pre = 0;

        int cur2 = 0;
        int pre2 = 0;
        //计算不偷最后一个房间的最大值
        for(int i = 0; i < nums.length - 1; i++){
            int temp = cur;
            cur = Math.max(cur, pre + nums[i]);
            pre = temp;
        }
        //计算不偷第一个房间的最大值
        for(int i = 1; i < nums.length; i++){
            int temp = cur2;
            cur2 = Math.max(cur2, pre2 + nums[i]);
            pre2 = temp;
        }

        return Math.max(cur, cur2);
    }
}

打家劫舍Ⅲ请见另一篇文章，使用树形DP。