从数组中按神奇顺序选出数后得到的最大和

Question

数组中有N个整数。如果你选择元素在索引"i"，然后你得到数组[i]值在你的包，数组[i]，数组[i-1]和数组[i+1]变成零，选择数组[i]后(即你不能再采取这些元素在下次选择)。

Answer 1

对于每个i，我们要么接受该项，要么忽略它。我们选择效果更好的方法。以下是dp方法:

const int N=10;
int a[]={1,2,3,4,5,6,7,8,9,10};
int dp[N];
int main() {
    dp[0]=a[0];
    dp[1]=max(a[0],a[1]);
    for(int i=2;i<N;i++) {
        dp[i]=max(dp[i-2]+a[i],dp[i-1]);  
        // dp[i-2]+a[i] is we include item i, hence we cannot take item i-1
        // dp[i-1] is we don't take item i
    }
    cout<<dp[N-1];
    return 0;
}