198. House Robber.md

198. House Robber

思路

思路一

简单动态规划。
设直到第i个街道小偷能获得最大的收益为dp[i], 有两种情况：

• 若不偷这个街区，则dp[i] = dp[i-1]；
• 若偷这个街区，则dp[i] = dp[i-2] + nums[i]。

即dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]).
时间复杂度和空间复杂度都为O(n)

思路一空间优化

很明显可以用动归常用的空间优化方法滚动数组来优化空间，即用pre记录dp[i-1]，空间复杂度为o(1)

思路二

还可以用更直观的方法，用两个变量 rob 和 notRob 分别表示抢当前的房子和不抢当前的房子所获最大钱数，那么在遍历的过程中，先用两个变量 preRob 和 preNotRob 来分别记录更新之前的值，则

• 由于 rob 是要抢当前的房子，那么前一个房子一定不能抢，即更新rob = preNotRob + nums[i];
• 然后 notRob 表示不能抢当前的房子，那么之前的房子就可以抢也可以不抢，即更新notRob = max(preRob, preNotRob)。

最后返回max(rob, notRob)即可。时间复杂度O(n)，空间复杂度也是O(1)

C++

思路一

class Solution {
public:
    int rob(vector<int>& nums){
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];
        vector<int>dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); i++) dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        return dp[nums.size() - 1];
    }
};

思路一空间优化

class Solution {
public:
    int rob(vector<int>& nums){
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];
        int tmp, res, pre = nums[0];
        res = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); i++) {
            tmp = res;
            res = max(res, pre + nums[i]);
            pre = tmp;
        }
        return res;
    }
};

思路二

class Solution {
public:
    int rob(vector<int>& nums) {
        int rob = 0, notRob = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            int preRob = rob, preNotRob = notRob;
            rob = preNotRob + nums[i];
            notRob = max(preRob, preNotRob);
        }
        return max(rob, notRob);
    }
};