leetcode 198. House Robber

2017-08-07

题意

强盗抢钱最大数：一溜家庭，强盗都能抢，但是如果抢了连续两个家庭的话就会被抓走。那怎么做到不被抓走，同时保证抢的数额最大。

我的思路

刚一开始我居然会觉得奇数下标数组之对比偶数下标数组之和就能得到了最大值。真是头脑简单。

想了一下午，想出来了O(∩_∩)O哈哈~,

通过等长状态数组来存到达每个位置的能抢的最大值。那怎么计算这个最大值呢，前两个好说，第一个数就是自己，第二个数和第一个对比取较大的就是第二个数的抢到的最大值。第三个数和第一个数存的最大状态值相加和第二个数的状态值对比，取较大值。

public int rob(int[] nums) {
    if(nums.length == 0) return 0;
    if(nums.length == 1) return nums[0];
    int[] maxs = new int[nums.length];
    maxs[0] =  nums[0];
    maxs[1] = nums[0]>nums[1]?nums[0]:nums[1];
    for(int i=2;i<nums.length;i++){
        maxs[i] = (nums[i]+maxs[i-2])>maxs[i-1]?(nums[i]+maxs[i-2]):maxs[i-1];
    }
    return maxs[nums.length-1];
}

大神代码

大意和我的一样，把前面的判断都融入了循环中，并只需记录两个状态值就行了。把空间复杂度降到了O(1)

public int rob(int[] num) {
    int prevNo = 0;
    int prevYes = 0;
    for (int n : num) {
        int temp = prevNo;
        prevNo = Math.max(prevNo, prevYes);
        prevYes = n + temp;
    }
    return Math.max(prevNo, prevYes);
}