题目描述

House Robber I
在连续的一排房子中进行盗窃活动，用一维数组来表示每个房子里面的财富值。规定不能盗窃挨着的两户人家，因为会招来警察。求能够盗窃得到的最大累积财富。

样例

example1:
input: [1,2,3,1]
output:4
explain：rob the houses which money are 1, 3 to get max 1 + 3 = 4.

example2:
input:[2,7,9,3,1]
output:11
explain:2 + 9 + 1 = 12

算法1

(动态规划) 时间$O(n)$, 空间$O(n)$

使用两个和nums数组一样长的数组：rob和not_rob。

其中的rob[i]代表对nums[i]进行了盗窃；not_rob[i]代表没有对nums[i]进行了盗窃。

由于每个房间只存在盗窃和未盗窃两种情况，所以只需要每次更新这两个数组中的值，然后到了末尾取最大值就可以了。

Java 代码

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 [] rob = new int[len];
        int [] not_rob = new int[len];
        rob[0] = nums[0]; not_rob[0] = 0;
        for(int i = 1;i < len;i++){
            rob[i] = not_rob[i-1] + nums[i];
            not_rob[i] = Math.max(not_rob[i-1], rob[i-1]);  //关键点，i-1天可以偷也可以不偷
        }
        return Math.max(rob[len-1], not_rob[len-1]);
    }
}

算法2

(动态规划) 时间$O(n)$, 空间$O(1)$

观察到上个算法中，其实每次在更新rob[i]和not_rob[i]的时候，只使用到了rob[i-1]和not_rob[i-1]

因此我们使用rob和not_rob来继续它们就可以了，然后不断更新它们俩的值。就不需要再维护数组了，最后取两者中最大值就可以了。

值得注意的是，在循环中，因为新更新了rob，所以在更新not_rob时，就找不到之前rob了，所以要用last_rob变量保存起来。

Java代码

//隔着至少一户人家，偷窃财富
public int rob(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int len = nums.length;
    if(len == 1) return nums[0];
    int rob = nums[0], not_rob = 0;
    for(int i = 1;i < len;i++){
        int last_rob = rob;
        rob = not_rob + nums[i];
        not_rob = Math.max(not_rob, last_rob);  //关键，i-1天可以偷也可以不偷
    }
    return Math.max(rob, not_rob);
}