题解 | #不相邻取数#

这是一个经典的动态规划 (Dynamic Programming) 问题，通常被称为最大不相邻子序列和或房屋偷盗问题 (House Robber Problem) 的变体。

动态规划解法

我们可以定义一个动态规划数组 $DP$ ，其中 $DP[i]$ 表示考虑数组的前 $i$ 个元素时，能得到的最大不相邻元素之和。

对于数组中的第 $i$ 个元素 $a_i$ （数组从 $1$ 开始索引），我们有两种选择：

选择 (取) $a_i$ ： 如果我们选择 $a_i$ ，那么我们不能选择前一个元素 $a_{i-1}$ 。此时，最大和是 $a_i$ 加上考虑前 $i-2$ 个元素时的最大和，即 $a_i + DP[i-2]$ 。
不选择 (不取) $a_i$ ： 如果我们不选择 $a_i$ ，那么最大和就是考虑前 $i-1$ 个元素时的最大和，即 $DP[i-1]$ 。

因此，状态转移方程为： $DP[i] = \max(DP[i-1], a_i + DP[i-2])$

初始状态 (Base Cases)

$i = 0$ (空数组): $DP[0] = 0$
$i = 1$ (只有一个元素 $a_1$ ): $DP[1] = a_1$
$i = 2$ (有两个元素 $a_1, a_2$ ): 只能取一个，所以 $DP[2] = \max(a_1, a_2)$ 。根据状态转移方程： $DP[2] = \max(DP[1], a_2 + DP[0]) = \max(a_1, a_2 + 0) = \max(a_1, a_2)$

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> dp(n);
    ll ans = 0;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;

        // 取a
        ll t1 = (i > 1 ? dp[i - 2] : 0) + a;
        // 不取a
        ll t2 = (i > 0 ? dp[i - 1] : 0);
        dp[i] = max(t1, t2);
        ans = max(ans, dp[i]);
    }

    cout << ans << endl;
}