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

题目描述

题目分析

S0,S1,S2,S3代表房屋的金额，H0,H1,H2,H3代表房屋。 第1间房屋：S0=H0=1 第2间房屋：S1=MAX(S0,H1)=2 第3间房屋：S2=MAX(S0+H2,S1)=4 第4间房屋：S3=MAX(S1+H3,S2)=4 递推公式：Sn=MAX(Sn-2+Hn,Sn-1) 偷窃前n-1间房屋的数量， 或是偷窃前n-2间房屋的数量加当前第n间房屋的数量。

时间复杂度：O(n) 空间复杂度：O(1)

代码

C++代码如下：

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