最长的斐波那契子序列的长度 图解题解

最长的斐波那契子序列，到底要在数组里找出什么

给一个严格递增的正整数数组 arr，要在里面挑一条最长的『斐波那契式』子序列。子序列指按原顺序、可跳着挑出的若干个数；斐波那契式要求长度至少为 3，且从第三个数起每数都等于前面两数之和。题面 arr=[1,2,3,4,5,6,7,8] 答案是 5，对应 [1,2,3,5,8]。

为什么把斐波那契子序列一条条列出来会算爆

数组里每个数选或不选，子序列就有 2ⁿ 条，逐条验是不是斐波那契式，n 才几十就数不完。斐波那契式有个硬性质：头两数一旦定死，后面每项由『前两项之和』唯一确定。可就算只枚举开头两数往后推，仍是 O(n²)（大 O，衡量运算量），每对还要往后核对、同段链反复重算。突破口是反过来：盯住末尾两数往前找前驱（前驱，就是斐波那契链里排在这两数前头的那个数）。

为什么要拿 arr[i]、arr[j] 两个下标才定得下状态

要复用子问题，先给它一个标识。斐波那契式的下一项由前两项决定，只记结尾是哪个数不够：同一个结尾数，前面搭的倒数第二个数不同，要求的前驱也不同。所以状态要锁住末尾两数：定义 dp[i][j] 为以中间数 arr[j]、末尾数 arr[i] 收尾的最长斐波那契式子序列长度（i、j 是下标，j 在前 i 在后）。dp 是动态规划的表（以 arr[i]、arr[j] 结尾的斐式链长算一次、存下复用）；只用一个下标，两条链会挤进同一格，转移就错。

定了末尾两数，前驱为什么正好是 arr[i]−arr[j]

末尾两数是中间的 arr[j] 和最后的 arr[i]，要在前头接的前驱须满足『前驱 + arr[j] = arr[i]』，值就是 arr[i] − arr[j]。剩下只问它在不在数组里、下标排不排在 arr[j] 前面，哈希表（『值 → 下标』一步可查）正合用。设前驱下标为 k，只要它在表里且 k 小于 j，就把以 arr[k]、arr[j] 结尾的那段接长一位：dp[i][j] = dp[j][k] + 1，否则自成长度 2（参考代码里 dp 表叫 f、哈希表叫 d）。

拿题面示例把这条最长链亲手接一遍

拿题面的 arr=[1,2,3,4,5,6,7,8] 走一遍，先把每个『值 → 下标』存进哈希表，相邻两数起手长度 2。中间数 2、末尾数 3：前驱 = 3 − 2 = 1，下标 0 靠前，把 1、2 那段接成 3。中间数 3、末尾数 5：前驱 = 5 − 3 = 2 靠前接成 4。中间数 5、末尾数 8：前驱 = 8 − 5 = 3 靠前接成 5。反例中间数 2、末尾数 4：前驱 = 4 − 2 = 2 虽在表里，下标恰是中间数 2 自己、不靠前，作废。枚举完最长 5，对应 [1,2,3,5,8]。

前驱明明在哈希表里，为什么这一对还是接不上

最容易栽的一处，是只顾查前驱在不在、忘了查位置。前驱下标必须严格排在中间数前面，也就是 k 小于 j；漏掉这关，会把前驱恰是中间数自己、或排在后头的情况当成合法，凑出不存在的链。另一处是别用二分找前驱：数值不按前驱排，二分没着力点。长度不足 3 返回 0。复杂度：枚举末尾两数 O(n²) 对，每对靠哈希把找前驱压到一步，空间 O(n²)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        f = [[0] * n for _ in range(n)]
        d = {x: i for i, x in enumerate(arr)}
        for i in range(n):
            for j in range(i):
                f[i][j] = 2
        ans = 0
        for i in range(2, n):
            for j in range(1, i):
                t = arr[i] - arr[j]
                if t in d and (k := d[t]) < j:
                    f[i][j] = max(f[i][j], f[j][k] + 1)
                    ans = max(ans, f[i][j])
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        int f[n][n];
        memset(f, 0, sizeof(f));
        unordered_map<int, int> d;
        for (int i = 0; i < n; ++i) {
            d[arr[i]] = i;
            for (int j = 0; j < i; ++j) {
                f[i][j] = 2;
            }
        }

        int ans = 0;
        for (int i = 2; i < n; ++i) {
            for (int j = 1; j < i; ++j) {
                int t = arr[i] - arr[j];
                auto it = d.find(t);
                if (it != d.end() && it->second < j) {
                    int k = it->second;
                    f[i][j] = max(f[i][j], f[j][k] + 1);
                    ans = max(ans, f[i][j]);
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] f = new int[n][n];
        Map<Integer, Integer> d = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            d.put(arr[i], i);
            for (int j = 0; j < i; ++j) {
                f[i][j] = 2;
            }
        }
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            for (int j = 1; j < i; ++j) {
                int t = arr[i] - arr[j];
                Integer k = d.get(t);
                if (k != null && k < j) {
                    f[i][j] = Math.max(f[i][j], f[j][k] + 1);
                    ans = Math.max(ans, f[i][j]);
                }
            }
        }
        return ans;
    }
}