题解 | 不相邻取数

不相邻取数的最小场景就是 间隔1个取数和间隔2个取数（间隔3个的可以看成是 2个间隔1个的取数，以此类推）

所以我们只需要记录 dp[i] = max{aiai​+dp[i-2] , aiai​+dp[i-3]}

最大值一定位于 n或者 n-1中（从1开始）

#include<stdio.h>

int main()
{
    long long n,dp[5]={0};
    scanf("%lld",&n);
    
    for(long long i=1;i<=n;++i)
    {
        scanf("%lld",&dp[i%5]);
        if(i>2)
            dp[i%5] = (dp[(i-2+5)%5]+dp[i%5])>(dp[(i-3+5)%5]+dp[i%5])?(dp[(i-2+5)%5]+dp[i%5]):(dp[(i-3+5)%5]+dp[i%5]);
    }
    printf("%lld",dp[(n-1+5)%5]>dp[n%5]?dp[(n-1+5)%5]:dp[n%5]);
    return 0;
}