leetcode解题: House Robber(198)

发表于 | 分类于

You are a professional robber planning to rob houses along a street.
Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

解法1: DP with O(N) time and O(N) space

应该考虑到是经典的DP问题，要求一个最大的解。那么首先dp数组的含义是dp[i]代表前i个房子能取得的最大值，
考虑第i个房子，如果抢第i个房子，那么第i-1个房子一定不能取，所以最大的值是dp[i - 2] + A[i]
如果不抢第i个房子，那么最大的值就是前一个房子能取得的最大值，状态方程dp[i] = max(dp[i - 1], dp[i - 2] + A[i])。
这种考虑第i个数字取或者不取得思路在其他dp问题中也经常见到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int rob(int[] nums) {
	if (nums == null || nums.length == 0) {
		return 0;
	}
	
	if (nums.length == 1) {
		return nums[0];
	}
	
	// initialize
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	dp[1] = Math.max(dp[0], nums[1]);
	
	// dp transition
	for (int i = 2; i < nums.length; i++) {
		dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
	}
	
	return dp[nums.length - 1];
}

解法1优化: DP with O(N) time and O(1) space

实际上观察状态方程可以发现，我们只需要记录dp[i - 2], dp[i -1]两个数值，所以可以维护一个数组{A,B,C},前两个数字作为buffer，不停更新三个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int rob(int[] nums) {
	if (nums == null || nums.length == 0) {
		return 0;
	}
	
	if (nums.length == 1) {
		return nums[0];
	}
	
	// initialize
	int[] dp = new int[]{nums[0], Math.max(nums[0], nums[1]), Math.max(nums[0], nums[1])};
	
	// dp transition
	for (int i = 2; i < nums.length; i++) {
		dp[2] = Math.max(dp[1], dp[0] + nums[i]);
		dp[0] = dp[1];
		dp[1] = dp[2];
	}
	
	return dp[2];
}