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个数字即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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]);
	}
}