LEETCODE 198. House Robber

佚名 6年前 (2019-04-18) 随笔 965人围观抢沙发百度已收录

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

这道题是典型的动态规划题，用空间换时间，将问题分解为小问题解决，每一次选择抢还是不抢取决于前一次和这次加上上上次的大小，如果抢了收益大，就抢。