题解 | 不相邻取数

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
int main() {
    ll n = 0;
    cin >> n;
    vector<ll>nums(n, 0);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    vector<ll>dp(n, 0);
    if (n == 1) {
        cout << nums[0] << endl;
    } else if (n == 2) {
        cout << max(nums[0], nums[1]) << endl;
 //在n==1和n==2的时候要特判，在一般情况下状态转移方程是在n>2的时候才可以用
//重点在状态转移方程：dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
    } else {
        dp[0] = nums[0];
        dp[1] = max(nums[1], nums[0]);
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
//这里我们分开来看
//在dp[i]这个状态，它有什么样的情况到达dp[i]这个状态
//dp[i-2]+nums[i]的意思是取当前的这一个nums[i]和上个不间隔的最优结果
//dp[i-1]是将nums[i]这个作为中间要要跳过的间隔，将nums[i]作为间隔，而上面这个是将nums[i-1]作为间隔所以取nums[i]为加。
        }
        cout << dp[dp.size() - 1] << endl;
    }
    return 0;
}