// f[i]表示偷 1~i 家的所有方案的最大收益
// 计算分为两种情况
// 如果偷第i家,那么第i-1家肯定不能偷,加上1~i-2家的最大方案f[i-2]
// 如果不偷第i家,那么就是f[i-1]
class Solution {
public:
int rob(vector<int>& nums) {
int n =nums.size();
vector<int> f(n + 1);
f[0] = 0;
for(int i = 1; i <= n; ++i){
f[i] = nums[i - 1]; // 因为nums数组下标从0开始,要减1
if(i >= 2) f[i] += f[i - 2];
f[i] = max(f[i], f[i - 1]);
}
return f[n];
}
};