假設(shè)你是一個專業(yè)的竊賊，準(zhǔn)備沿著一條街打劫房屋。每個房子都存放著特定金額的錢。你面臨的唯一約束條件是：相鄰的房子裝著相互聯(lián)系的防盜系統(tǒng)，且 當(dāng)相鄰的兩個房子同一天被打劫時，該系統(tǒng)會自動報警。

給定一個非負(fù)整數(shù)列表，表示每個房子中存放的錢， 算一算，如果今晚去打劫，你最多可以得到多少錢 在不觸動報警裝置的情況下。

樣例
給定 [3, 8, 4], 返回 8.

挑戰(zhàn)
O(n) 時間復(fù)雜度 且 O(1) 存儲。

分析:

定義dp[i]表示打劫第i個房間為止所獲得的最大收益，而dp[i]的值只與dp[i-2] 和dp[i-3]有關(guān) 并且 dp[i] = A[i] + max(dp[i-2],dp[i-3])

當(dāng)求解所有的A[i]后，需要對最后兩個dp[len-1] dp[len-2] 取最大值作為最后的答案,因為存儲的且 O(1) ,又dp關(guān)系僅限于4個數(shù)字之間，因此只用4個數(shù)字即可。

代碼:

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]);
    }
}