# 题目描述
# 思路与题解
和前面题的思路蛮像的，关键在于比大小，因为题目有不能偷盗相邻的两个房间的限制，所以比大小的关键就是 max(dp[i-1], dp[i-2] + nums[i]) ，dp [i] 就表示新增了第 i 个房间后的最大收益，所以如果我第 i 个房间不偷，我能得到的最大收益就是 dp [i-1]；如果我第 i 个房间偷了，那我 i-1 房间就不能偷了，所以我能得的最大收益就是 dp [i-2] + nums [i]，是不是很 easy~~
当然啦，再稍微思考一下，可以用滚动数组把空间复杂度优化为 O (1)
class Solution { | |
public: | |
int rob(vector<int>& nums) { | |
int n = nums.size(); | |
int dp[n]; | |
dp[0] = nums[0]; | |
if (n < 2) { | |
return dp[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(); | |
if (n < 2) { | |
return nums[0]; | |
} | |
int prev = 0, curr = nums[0]; | |
for (int i = 1; i < n; ++i) { | |
int next = max(curr, prev + nums[i]); | |
prev = curr; | |
curr = next; | |
} | |
return curr; | |
} | |
}; |
