image.png
（图片来源https://leetcode.com/problems/house-robber/
）
| 日期 | 是否一次通过 | comment |
|---|---|---|
| 2019-12-01 |
留意下：
res[i] = max(res[i-2]+num[i], res[i-1])
有点类似斐波那契问题。
/** 遍历 */
public int rob(int[] nums) {
if(nums == null || nums.length <= 0) {
return 0;
}
int[] memo = new int[nums.length+1];
memo[0] = 0;
memo[1] = nums[0];
for(int i=1; i<nums.length ; i++) {
memo[i+1] = Math.max(memo[i], memo[i-1]+nums[i]);
}
return memo[nums.length];
}
/** 遍历 */
public int rob2(int[] nums) {
if (nums.length == 0) {
return 0;
}
int prev1 = 0;
int prev2 = 0;
for (int num : nums) {
int tmp = prev1;
prev1 = Math.max(prev2 + num, prev1);
prev2 = tmp;
}
return prev1;
}
/** 暴力递归 */
public int rob1(int[] nums) {
return helper(nums, nums.length - 1);
}
private int helper(int[] nums, int i) {
if (i < 0) {
return 0;
}
return Math.max(helper(nums, i - 2) + nums[i], helper(nums, i - 1));
}
