Leetcode198:打家劫舍（动态规划、滚动数组）

来源

方法1：动态规划

money[i] 表示有i个房子，偷的钱最多

money[i]= max{money[i-1], nums[i]+money[i-2]}

 1 class Solution {
 2     public int rob(int[] nums) {
 3         int n = nums.length;
 4         int[] money = new int[n];
 5         if(n==1) {
 6             return nums[0];
 7         }
 8         if(n==2){
 9             return Math.max(nums[0],nums[1]);
10         }
11         money[0] = nums[0];
12         money[1] = Math.max(nums[0],nums[1]);
13 
14         for(int i = 2; i){
15             money[i] = Math.max(money[i-1],money[i-2]+nums[i]);
16         }
17         return money[n-1];
18     }
19 }

方法2：滚动数组（继动态规划的优化）

money[i]= max{money[i-1], nums[i]+money[i-2]}

由于money[i]只与前两项有关，所以可以用滚动数组动态维护前两项

 1 class Solution {
 2     public int rob(int[] nums) {
 3         int n = nums.length;
 4         if(n==1) {
 5             return nums[0];
 6         }
 7         if(n==2){
 8             return Math.max(nums[0],nums[1]);
 9         }
10         int pre_pre = nums[0];//money[i-2]
11         int pre= Math.max(nums[0],nums[1]);//money[i-1]
12         int tmp = 0;
13         for(int i = 2; i){
14             tmp = pre;
15             pre = Math.max(pre, pre_pre+nums[i]);
16             pre_pre = tmp;
17         }
18         return pre;
19     }
20 }