题解 | 不相邻取数

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n ;
    cin>>n;
    vector<int> nums(n);
    for(int i = 0 ; i < n ; i++ ){
        cin>>nums[i];
    }


    //dp[i]表示前n个最大和
    //dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = nums[0];
    for(int i = 2; i<n+1;i++){
        dp[i] = max(dp[i-2]+nums[i-1],dp[i-1]);
    }

    cout<<dp[n]<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

类似打家劫舍