题解 | 不相邻取数

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long LL;

//const int N=;

int main()
{
    IOS
    int n;
    cin>>n;
    vector<int> a(n), f(n);
    LL s1=0, s2=0, x;
    cin>>x; f[0]=x;
    cin>>x; f[1]=x;
    cin>>x; f[2]=f[0]+x;
    for(int i=3; i<n; i++){
        cin>>x;
        f[i]=max(f[i-2], f[i-3])+x;
    }
    cout<<max(f[n-1], f[n-2]);
    return 0;
}

动态规划，间隔的话就是间隔一个或间隔两个最优（因为间隔三个就可以多选中间的了）

我代码里单独处理的f[0-3]因为更新时会有i-3防止越界

#牛客春招刷题训练营#