孩子，这道题是 “状态压缩”与“降维打击” 的经典博弈。在类斐波那契序列中，三元关系 $A[k] + A[j] = A[i]$ 是核心。

下面我按算法进阶的顺序，为你提供三个版本的完整代码，并分析其演变过程。

版本 1：暴力搜索（适合初学者，预计得分 30-50%）

思路： 既然序列由前两项决定，我们就枚举数组中任意两个数作为序列的“种子”，然后按照斐波那契规则不断向后寻找。 时间复杂度： $O(N^3)$；空间复杂度： $O(1)$。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 版本 1: 暴力枚举起点种子 O(N^3)
int solve_v1(int n, vector<int>& nums) {
    int max_len = 0;
    // 枚举序列的第一项和第二项
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int a = nums[i];
            int b = nums[j];
            int curr_len = 2;
            // 按照规则在剩余部分寻找 a + b
            // 注意：因为数组递增，可以使用 binary_search 提速至 O(N^2 log N)
            while (true) {
                int next_val = a + b;
                // 在 j 之后寻找 next_val
                if (binary_search(nums.begin() + j + 1, nums.end(), next_val)) {
                    curr_len++;
                    a = b;
                    b = next_val;
                } else {
                    break;
                }
            }
            if (curr_len >= 3) max_len = max(max_len, curr_len);
        }
    }
    return max_len;
}

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

版本 2：哈希表优化 DP（资料推荐做法，预计得分 100%）

思路： 引入二维 DP。dp[j][i] 表示以索引 $j$ 和 $i$ 结尾的类斐波那契序列长度。 转移方程： 找到 $k$ 使得 $nums[k] = nums[i] - nums[j]$ 且 $k < j$，则 dp[j][i] = dp[k][j] + 1。 时间复杂度： 平均 $O(N^2)$；空间复杂度： $O(N^2)$。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 全局静态数组，2500*2500 占用约 25MB 内存，NOIP 建议放在全局
int dp[2505][2505];

// 版本 2: 哈希表辅助 DP O(N^2)
int solve_v2(int n, vector<int>& nums) {
    // 预处理数值到索引的映射，实现 O(1) 查找 k
    unordered_map<int, int> val_to_idx;
    for (int i = 0; i < n; ++i) val_to_idx[nums[i]] = i;

    int max_len = 0;
    
    // 初始化：任何两项都可以视为长度为 2 的序列起点
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j) dp[j][i] = 2;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int target = nums[i] - nums[j];
            // 易错点：必须保证 target < nums[j] (因为数组递增，即保证索引 k < j)
            // 且 target 必须在数组中存在
            if (target < nums[j] && val_to_idx.count(target)) {
                int k = val_to_idx[target];
                dp[j][i] = dp[k][j] + 1;
                max_len = max(max_len, dp[j][i]);
            }
        }
    }
    return max_len >= 3 ? max_len : 0;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];
    cout << solve_v2(n, nums) << endl;
    return 0;
}

版本 3：双指针优化 DP（最优常数版，适合 $N$ 较大时）

思路： 既然 nums 是严格递增的，对于固定的 $i$，当 $j$ 减小时，$target = nums[i] - nums[j]$ 会增大。我们可以用左右双指针在 $O(N)$ 内处理完所有的 $j$。 优点： 彻底抛弃哈希表，常数极小，且空间利用率高。 时间复杂度： 严格 $O(N^2)$；空间复杂度： $O(N^2)$。

#include <iostream>
#include <vector>

using namespace std;

int f[2505][2505]; // f[j][i]

int solve_v3(int n, vector<int>& nums) {
    int max_len = 0;
    // 技巧：i 作为序列最后一项
    for (int i = 2; i < n; ++i) {
        int left = 0, right = i - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < nums[i]) {
                left++; // 和太小，左指针右移
            } else if (sum > nums[i]) {
                right--; // 和太大，右指针左移
            } else {
                // 刚好满足：nums[left] + nums[right] = nums[i]
                // 此时 k=left, j=right
                f[right][i] = (f[left][right] > 0 ? f[left][right] : 2) + 1;
                max_len = max(max_len, f[right][i]);
                left++;
                right--;
            }
        }
    }
    return max_len;
}

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; ++i) cin >> a[i];
    cout << solve_v3(n, a) << endl;
    return 0;
}

复杂度分析思考过程

1. 为什么需要二维 DP？ 一维 DP 只能代表“以 $i$ 结尾的最优解”。但在类斐波那契中，同样是以数字 8 结尾，[1, 7, 8] 和 [3, 5, 8] 是完全不同的序列。增加一维 j（前一项）是为了锁死序列的公和关系。

2. 空间换时间的权衡：

   • $N=2500$ 时，$N^2 \approx 6.25 \times 10^6$。
   • 使用 int 数组占用约 25MB，远低于常见的 128MB 限制。
   • 如果 $N$ 增加到 $10000$，我们需要考虑使用哈希表（只存存在的对）或滚动数组（如果可能）。

时间复杂度优化建议

1. 哈希表 vs 二分查找：
   • 如果 $A[i]$ 范围很大但 $N$ 很小，哈希表（unordered_map）表现良好。
   • 但在 NOIP 竞赛中，如果数组有序且数据密集，双指针 (Version 3) 的常数是最小的，通常比哈希表快 3-5 倍。
2. 提前终止：
   • 在双指针扫描时，如果 nums[left] * 2 > nums[i]，说明不可能再找到满足条件的 left 和 right（因为 $nums[left] < nums[right]$），可以提前跳出。

教练寄语： 孩子，记住：子序列问题的维度通常取决于它“回看”了多少项。 既然类斐波那契要看两项，那就给它两个维度。掌握了这个“升维”思想，你就掌握了复杂 DP 的命门。