873. 最长的斐波那契子序列的长度

发表于 分类于 阅读次数： Waline： 本文字数： 935 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

1. 问题描述与建模

给定一个严格递增的整数数组： \[ \text{arr} = [a_0, a_1, \dots, a_{n-1}] \] 要求找出其中最长的 Fibonacci-like 子序列长度。

Fibonacci-like 子序列满足以下条件：

  • 子序列长度至少为 \(3\)；
  • 对任意连续三个元素 \((x, y, z)\)，满足：

\[ x + y = z \]

  • 子序列不要求连续，但必须保持原数组中的相对顺序。

2. 关键观察：为什么一维状态不够？

一个自然但错误的直觉是尝试定义：

“以某个值结尾的最长 Fibonacci 子序列长度”

例如设： \[ f[x] = \text{以值 } x \text{ 结尾的最长 Fibonacci-like 子序列长度} \] 但这种状态信息不足，原因在于：

  • Fibonacci 递推关系依赖的是最后两个数，而不是最后一个数；
  • 即使两个子序列都“以 \(x\) 结尾”，它们的倒数第二个元素不同，能否继续扩展完全不同。

换言之：

是否可以接上下一个数 \(z\)，取决于 \((\text{倒数第二个}, \text{倒数第一个})\) 这一个有序对。

因此，仅记录最后一个元素会丢失关键信息，必然导致错误拼接。

3. 正确建模：二维状态定义

为完整描述 Fibonacci 子序列的结构，必须显式记录最后两个元素。

状态定义

设： \[ f[j][i] = \text{以 } a_j, a_i \text{ 为最后两个元素的最长 Fibonacci-like 子序列长度} \] 其中：

  • \(0 \le j < i < n\)；
  • 默认情况下，任意一对 \((a_j, a_i)\) 至少可以构成长度为 \(2\) 的“序列”。

因此初始化为： \[ f[j][i] = 2 \]

4. 状态转移方程推导

考虑如何从已有状态转移到 \(f[j][i]\)。

转移条件

若存在一个下标 \(k\)，满足： \[ a_k + a_j = a_i \] 且： \[ k < j < i \] 则可以将以 \((a_k, a_j)\) 结尾的 Fibonacci 子序列，扩展一个元素 \(a_i\)。

转移方程

此时有： \[ f[j][i] = f[k][j] + 1 \] 这是一个标准的“接在末尾”型 DP 转移。

下标合法性的保证

由于原数组严格递增： \[ a_0 < a_1 < \dots < a_{n-1} \] 若： \[ a_k = a_i - a_j < a_j \] 则必然有： \[ k < j \] 因此在实现中，只要保证： \[ a_j \times 2 > a_i \] 就可以隐式保证 \(k < j\)，并进行剪枝优化。

5. 算法流程

整体流程如下：

  1. 使用哈希表 pos，将数组值映射到其下标，便于 \(O(1)\) 查询；
  2. 初始化二维 DP 数组 f[j][i] = 2；
  3. 枚举右端点 \(i\)；
  4. 枚举左端点 \(j < i\)，并利用有序性剪枝；
  5. 若存在 \(k\) 使 \(a_k + a_j = a_i\)，更新：

\[ f[j][i] = f[k][j] + 1 \]

  1. 全程维护最大值作为答案。

6. 时间与空间复杂度

  • 时间复杂度： 最外层 \(O(n)\)，内层 \(O(n)\)，总体为：

\[ O(n^2) \]

  • 空间复杂度：

\[ O(n^2) \]

用于存储二维 DP 状态。

7. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        int mx = 0;

        // pos[value] = index，用于 O(1) 查找某个值的位置
        unordered_map<int, int> pos;
        for (int i = 0; i < n; ++i) {
            pos[arr[i]] = i;
        }

        // f[j][i] 表示以 arr[j], arr[i] 为最后两个元素的
        // 最长 Fibonacci-like 子序列长度
        // 任意一对至少为 2
        vector<vector<int>> f(n, vector<int>(n, 2));

        for (int i = 0; i < n; ++i) {
            int x = arr[i];
            // 倒序枚举 j，并利用有序性剪枝：
            // 只有当 arr[j] * 2 > x 时，才可能存在 k < j
            for (int j = i - 1; j >= 0 && arr[j] * 2 > x; --j) {
                int need = x - arr[j];
                auto it = pos.find(need);
                if (it == pos.end()) {
                    continue;  // 不存在这样的 k
                }

                int k = it->second;
                // 此时 need < arr[j]，数组严格递增 => k < j 一定成立
                f[j][i] = f[k][j] + 1;
                mx = max(mx, f[j][i]);
            }
        }

        // 若不存在合法 Fibonacci 子序列，mx 会保持为 0
        return mx;
    }
};