LintCode 打劫房屋

假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。

给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。

样例
给定 [3, 8, 4], 返回 8.

挑战
O(n) 时间复杂度 且 O(1) 存储。

分析:

定义dp[i]表示打劫第i个房间为止所获得的最大收益，而dp[i]的值只与dp[i-2] 和dp[i-3]有关 并且 dp[i] = A[i] + max(dp[i-2],dp[i-3])

当求解所有的A[i]后，需要对最后两个dp[len-1] dp[len-2] 取最大值作为最后的答案,因为存储的且 O(1) ,又dp关系仅限于4个数字之间，因此只用4个数字即可。

代码:

public class Solution {
    /**
     * @param A: An array of non-negative integers.
     * return: The maximum amount of money you can rob tonight
     */
    public long houseRobber(int[] houseMoneys) {
        if(null == houseMoneys || houseMoneys.length <= 0)
            return 0;
        if(houseMoneys.length == 1)
            return houseMoneys[0];
        if(houseMoneys.length == 2)
        {
            return Math.max(houseMoneys[0], houseMoneys[1]);
        }
        
        if(houseMoneys.length == 3)
        {
            return Math.max(houseMoneys[1], houseMoneys[0] + houseMoneys[2]);
        }
        
        long[] max = new long[4];
        max[0] = houseMoneys[0];
        max[1] = houseMoneys[1];
        max[2] = Math.max(houseMoneys[1], houseMoneys[0] + houseMoneys[2]);
        
        for(int i = 3;i < houseMoneys.length;i++)
        {
            max[3] = houseMoneys[i] + Math.max(max[0], max[1]);
            if(i == houseMoneys.length - 1)
                continue;
            max[0] = max[1];
            max[1] = max[2];
            max[2] = max[3];
        }
        
        return Math.max(max[3], max[2]);
    }
}