House Robber
1. 问题描述
ou 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.
2. 求解
方法一递归法
递归法如下图所示，从第0家开始，偷与不偷有两种情况，如果偷了则从第2家开始重复此过程，如果没偷，从第1家开始重复此过程，直至结束。
public class Solution
public int rob(int[] nums) {
if(nums.length == 0) {
return 0;
}
return robot(0, nums);
}
public int robot(int start, int[] nums) {
if(start >= nums.length) {
return 0;
}
int left = nums[start] + robot(start + 2, nums);
int right = 0 + robot(start + 1, nums);
int max = Math.max(left, right);
return max;
}
}Leetcode运行超时，说明存在优化空间。
方法二递归法+缓存
从图中可以看出，上述过程中会有重复的计算，例如从第二家开始偷的情况计算了两次，我们可以用一个HashMap将计算过的数据保存起来，去掉冗余计算。
public class Solution {
public static Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
public int rob(int[] nums) {
cache.clear();
if(nums.length == 0) {
return 0;
}
return robot(0, nums);
}
public int robot(int start, int[] nums) {
if(start >= nums.length) {
return 0;
}
if(cache.containsKey(start)) {
return cache.get(start);
}
int left = nums[start] + robot(start + 2, nums);
int right = 0 + robot(start + 1, nums);
int max = Math.max(left, right);
cache.put(start, max);
return max;
}
}方法三：非递归
将递归改造成非递归。
public class Solution {
public static Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
public int rob(int[] nums) {
cache.clear();
if(nums.length == 0) {
return 0;
}
int n = nums.length;
cache.put(n-1, nums[n - 1]);
for(int i = n - 2; i >=0; i--) {
int a = nums[i] + (cache.containsKey(i + 2) ? cache.get(i + 2) : 0);
int b = cache.containsKey(i + 1) ? cache.get(i + 1) : 0;
int max = Math.max(a, b);
cache.put(i, max);
}
return cache.get(0);
}
}**方法四：**HashMap变为数组
为了节省空间，可以将HashMap变为数组，代码也可以进一步优化，去掉三目运算符。
public class Solution {
public int rob(int[] nums) {
if(nums.length == 0) {
return 0;
}
if(nums.length == 1) {
return nums[0];
}
if(nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
int n = nums.length;
int[] cache = new int[n];
cache[n - 1] = nums[n - 1];
cache[n - 2] = Math.max(nums[n - 1], nums[n - 2]);
for(int i = n - 3; i >=0; i--) {
cache[i] = Math.max(nums[i] + cache[i + 2], cache[i + 1]);
}
return cache[0];
}
}