原题链接：https://leetcode.com/problems/house-robber/description/
这道题目有意思哦：
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
int[] nums = new int[]{49, 38, 65, 97, 76, 13, 27, 49};
System.out.println(s.rob2(nums));
}
/**
* 方法三：动态规划，迭代版本
*
* Submission Detail: 100.00%
* Runtime: 0 ms
*
* @param nums
* @return
*/
public int rob(int[] nums) {
if (nums == null || nums.length < 1) {
return 0;
}
int curr = 0, prev = 0, prevPrev = 0;
for (int i = 0; i < nums.length; i++) {
curr = Math.max(prev, prevPrev + nums[i]);
prevPrev = prev;
prev = curr;
}
return curr;
}
/**
* 方法二：动态规划，迭代版本，以空间换时间
*
* Submission Detail: 25.35%
* Runtime: 1 ms
*
* 从上面的运行结果来看，跟最优答案还有很大差距。。。然后我就去看了下最优答案：其实思路差不多，只不过用两个变量来代替数组，见方法三
*
* @param nums
* @return
*/
public int rob2(int[] nums) {
if (nums == null || nums.length < 1) {
return 0;
}
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (i == 0) {
res[i] = nums[0];
} else if (i == 1) {
res[i] = Math.max(nums[0], nums[1]);
} else {
res[i] = Math.max(res[i - 1], res[i - 2] + nums[i]);
}
}
return res[nums.length - 1];
}
/**
* 方法一：动态规划，递归实现版本
*
* Submission Result: Time Limit Exceeded
*
* @param nums
* @return
*/
public int rob1(int[] nums) {
if (nums == null || nums.length < 1) {
return 0;
}
return robHelper(nums, nums.length);
}
private int robHelper(int[] nums, int n) {
if (n == 1) {
return nums[0];
}
if (n == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robHelper(nums, n - 1), robHelper(nums, n - 2) + nums[n - 1]);
}
}