LeetCode198.打家劫舍（动态规划）

题目描述：来自LeetCode

 思路：这道题和01背包很像，这件房屋偷不偷跟前一间房屋是否偷了有关，比如说这是第i间房屋，如果第i-1间房屋偷了，那第i间房屋就不能再偷，那最大值就跟前i-1间房屋的金额最大值有关，如果第i-1间房屋没偷，那第i间房屋就可能要偷，且最大值跟前i-2间房屋有关，每一天偷与不偷，都跟前面的最大值有关，故可写出状态转移方程dp[i]=max(dp[i-1],dp[i-2]+nums[2])，特殊的，当只有一间房屋，则一定偷，且最大值为dp[0]=nums[0],当只有两件房屋，那一定是偷一间，且偷最大的那间，dp[1]=max(dp[0],dp[1])

int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;//没有房屋可偷
        int n=nums.size();
        if(n==1) return nums[0];//只有一间
        vector<int> dp=vector<int>(n,0);
        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[n-1];
    }

优化，空间复杂度O(N)到O(1)

我们从状态转移方程可以发现，第i间房屋偷不偷只与第i-1天和第i-2天有关，因此，我们可以用滚动数组，只记录第i-1和第i-2天的最大值即可

int rob(vector<int>& nums) {
        int beforeyesterday,yesterday;//前天i-2,昨天i-1
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        beforeyesterday=nums[0];
        yesterday=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++){
            int tmp=yesterday;
            yesterday=max(beforeyesterday+nums[i],yesterday);
            beforeyesterday=tmp;
        }
        return yesterday;
    }