题解 | #打家劫舍(二)# 活用容器

经典问题很多书上都有，比起通常解法用了std的deque容器，可以更方便地操作头尾，不用处理麻烦的下标。

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int calc(vector<int>& dp,deque<int>& houses){
    int i;
    dp[0]=houses[0];
    dp[1]=houses[1];
    for(i=2;i<dp.size();++i){
        dp[i]=max(dp[i-1],dp[i-2]+houses[i]);
    }

    return dp[dp.size()-1];
}
int main() {
    int n,t,result1,result2;
    cin>>n;
    deque<int> houses;
    vector<int> dp(n-1);
    while(--n){
        cin>>t;
        houses.push_back(t);
    }
    result1=calc(dp,houses);
    cin>>t;
    houses.push_back(t);
    houses.pop_front();
    result2=calc(dp,houses);
    cout<<max(result1,result2)<<endl;

}
// 64 位输出请用 printf("%lld")