打家劫舍

动态规划 递归 记忆化搜索

原始递归

class Solution {
public:
    int rob(vector<int>& nums) {
        return max(_rob(nums, 0, nums[0], true), _rob(nums, 0, 0, false));
    }
 
    int _rob(vector<int>& nums, int id, int amount, bool isSteal) {
        if(id+1 == nums.size()) return amount;
        if(isSteal) {
            return _rob(nums, id+1, amount, false);
        } else {
            return max(_rob(nums, id+1, amount+nums[id+1], true), _rob(nums, id+1, amount, false));
        }
    }
};

这是最开始的递归写法，里头有几个注意点：

• 不要笨笨的 isSteal，偷了就是上上个状态直接加
• 一般来说，递归倒着来，递推正着走，我这个写法是递归正着走了，但是好像无妨
• 加一层记忆化搜索就能过了

原始递归的记忆化搜索

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

注意记忆化搜索可以按这个模板写，直接当下的结果当下记

自己想出来的递推

凭自己的能力想出来了，发现动态规划还是需要根据题目找到隐含的条件，比如这里的条件就是，

• 中间最多只会连续不偷两间
• 头尾两个一定是偷不偷来会变

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

想法是，如果我现在偷，就是前一个不偷或者前两个不偷中的较大者 (这也说明了之前一定是子问题的最优解了)

如果现在不偷，我也只需要考虑维护上一个偷的情况，因为上一个不偷的情况，不会通过我来索引，而是 i-2 来索引

倒推递归的思路

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

这是当采纳了那个倒推的思路后的代码，同样采用记忆化会通过

官方的递推解

然后再考虑改为递推解，前面的正推递归因为透支未来计算，

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

进一步节省空间

注意到当前情况只与前两个情况相关，所以可以只要两个空间

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