题解 | #不相邻取数#

动态规划方程为m[i]=max(m[i-1],m[i-2]+a[i)]，首先将m[0]和m[1]初始化一下，之后其他项就可以用方程解。

#include<iostream>
using namespace std;
int main()
{
    int n,i,j;
    cin>>n;
    long long  a[100000];
    for(i=0;i<n;++i)
    {
        cin>>a[i];
    }
    long long m[100000];
    m[0]=a[0];
    m[1]=max(a[0],a[1]);
    for(int i=2;i<n;i++)
    {
        m[i]=max(m[i-1],m[i-2]+a[i]);
    }
    cout<<m[n-1];
}