【LeetCode】198. 打家劫舍 递归递推

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2:

输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/house-robber 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目很简单，递归就超时了，，，，但是很容易想到了递归，

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

接着就是把递归转成递推

选第三个，就可以选第一个。

或者不选第三个。

依次类推

first表示第一个数据

second表示第二个数据

nums[i]表示第三个数据

看第二个数据和第一个加第三个那个大，那个大就存那个，然后第二个数据就变成了第一个数据

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