题解 | #不相邻取数#

解题思路：

• 此题必须空间优化，一般情况：$dp[i]=max(dp[i-2]+v[i],dp[i-1])dp[i]\; =\; max(dp[i-2]+v[i],dp[i-1])$

#include<bits/stdc++.h>
using namespace std;
//超内存
// long long solve(vector<int> v, int i, vector<long long> &dp){
//     if(dp[i] != 0) return dp[i];
//     if(i == 0) dp[i] = v[i];
//     else if(i == 1) dp[i] = max(v[i-1],v[i]);
//     else dp[i] = max(solve(v, i-1,dp),solve(v, i-2, dp)+v[i]);
//     return dp[i];
// }
long long solve(vector<int> v, int n){//迭代更新，压缩空间
    long long dp , res ;
    if (n == 1) return v[n-1];
    else{
        dp = max(v[0],v[1]);
        res = v[0];
    }
    for(int i = 2; i < n; ++i){
        long long tmp = dp;
        dp = max(res+v[i], dp);
        res = tmp;
    }
    return dp;
}
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        cin>>v[i];
    }
    cout<<solve(v,n)<<endl;
    return 0;
}