§1

题目描述

严格递增数组 arr。子序列 x1,x2,...,xn 是斐波那契式的，需满足 n ≥ 3 且每一项都等于前两项之和。求最长斐波那契式子序列的长度，不存在返回 0。子序列可跳着选，但要保持原顺序。

输入 = arr=[1,2,3,4,5,6,7,8]　输出 = 5 （子序列 [1,2,3,5,8]）

输入 = arr=[1,3,7,11,12,14,18]　输出 = 3 （如 [1,11,12]）

§2

思路解析动画文字版

记住这套「固定末尾两数、往前找前驱 t = arr[i] − arr[j]、查哈希接长一位」，下面每一帧都在套它。

开局：左边是严格递增的数组，右边哈希表记录每个「值 → 下标」。接下来枚举末尾两个数 arr[j]（中间数，蓝指针）和 arr[i]（末尾数，紫指针），j 在 i 前面，逐对找前驱。

固定中间数 arr[1]=2（蓝）和末尾数 arr[2]=3（紫）。要在它们前面接一个数，必须满足前驱 + 2 = 3，所以前驱 t = 3 − 2 = 1。去哈希表查 1 在不在。

哈希里命中 1，它在下标 0（绿），而且 0 排在 1 前面，顺序合法。于是把以 (1,2) 结尾的那段长度 2 接长一位：dp(2,3) = 3。比旧的最长还长，ans 刷新成 3。

固定中间数 arr[1]=2（蓝）和末尾数 arr[3]=4（紫）。要在它们前面接一个数，必须满足前驱 + 2 = 4，所以前驱 t = 4 − 2 = 2。去哈希表查 2 在不在。

哈希里虽然有 2，但它在下标 1（红），并不排在中间数 arr[1] 的前面，凑不成「t, 2, 4」这种从左到右的合法顺序，这对作废，dp 保持长度 2。

固定中间数 arr[2]=3（蓝）和末尾数 arr[3]=4（紫）。要在它们前面接一个数，必须满足前驱 + 3 = 4，所以前驱 t = 4 − 3 = 1。去哈希表查 1 在不在。

哈希里命中 1，它在下标 0（绿），而且 0 排在 2 前面，顺序合法。于是把以 (1,3) 结尾的那段长度 2 接长一位：dp(3,4) = 3。没超过当前最长 ans=3，ans 不变。

固定中间数 arr[1]=2（蓝）和末尾数 arr[4]=5（紫）。要在它们前面接一个数，必须满足前驱 + 2 = 5，所以前驱 t = 5 − 2 = 3。去哈希表查 3 在不在。

哈希里虽然有 3，但它在下标 2（红），并不排在中间数 arr[1] 的前面，凑不成「t, 2, 5」这种从左到右的合法顺序，这对作废，dp 保持长度 2。

固定中间数 arr[2]=3（蓝）和末尾数 arr[4]=5（紫）。要在它们前面接一个数，必须满足前驱 + 3 = 5，所以前驱 t = 5 − 3 = 2。去哈希表查 2 在不在。

哈希里命中 2，它在下标 1（绿），而且 1 排在 2 前面，顺序合法。于是把以 (2,3) 结尾的那段长度 3 接长一位：dp(3,5) = 4。比旧的最长还长，ans 刷新成 4。

固定中间数 arr[3]=4（蓝）和末尾数 arr[4]=5（紫）。要在它们前面接一个数，必须满足前驱 + 4 = 5，所以前驱 t = 5 − 4 = 1。去哈希表查 1 在不在。

哈希里命中 1，它在下标 0（绿），而且 0 排在 3 前面，顺序合法。于是把以 (1,4) 结尾的那段长度 2 接长一位：dp(4,5) = 3。没超过当前最长 ans=4，ans 不变。

固定中间数 arr[1]=2（蓝）和末尾数 arr[5]=8（紫）。要在它们前面接一个数，必须满足前驱 + 2 = 8，所以前驱 t = 8 − 2 = 6。去哈希表查 6 在不在。

去哈希表查 6，整个数组里根本没有这个数，说明 2 和 8 前面接不上合法的前驱，这一对只能停在长度 2。

固定中间数 arr[2]=3（蓝）和末尾数 arr[5]=8（紫）。要在它们前面接一个数，必须满足前驱 + 3 = 8，所以前驱 t = 8 − 3 = 5。去哈希表查 5 在不在。

哈希里虽然有 5，但它在下标 4（红），并不排在中间数 arr[2] 的前面，凑不成「t, 3, 8」这种从左到右的合法顺序，这对作废，dp 保持长度 2。

固定中间数 arr[3]=4（蓝）和末尾数 arr[5]=8（紫）。要在它们前面接一个数，必须满足前驱 + 4 = 8，所以前驱 t = 8 − 4 = 4。去哈希表查 4 在不在。

哈希里虽然有 4，但它在下标 3（红），并不排在中间数 arr[3] 的前面，凑不成「t, 4, 8」这种从左到右的合法顺序，这对作废，dp 保持长度 2。

固定中间数 arr[4]=5（蓝）和末尾数 arr[5]=8（紫）。要在它们前面接一个数，必须满足前驱 + 5 = 8，所以前驱 t = 8 − 5 = 3。去哈希表查 3 在不在。

哈希里命中 3，它在下标 2（绿），而且 2 排在 4 前面，顺序合法。于是把以 (3,5) 结尾的那段长度 4 接长一位：dp(5,8) = 5。比旧的最长还长，ans 刷新成 5。

枚举完所有末尾两数对，最长的一条是绿色这 5 个：1、2、3、5、8。它们环环相扣，1+2=3、2+3=5、3+5=8，正好是斐波那契式，答案就是 5。灰掉的 4 没被选进这条链。

边界先想清：能凑出三连就是 3；凑不出任何 a+b=c 就返回 0。

两个高频追问：为何盯末尾两数、复杂度能否再降。

§3

参考代码

from __future__ import annotationsfrom 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

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n²)，枚举所有末尾两数对，每对查哈希 O(1)
空间：O(n²)，dp 表 n×n，外加 O(n) 哈希表

§5

易错点

✗ 错误写法：前驱下标 k 不要求在 j 前面

✓ 正确写法：必须 k 在 j 前面（k 小于 j）

三个数下标要从左到右严格递增，才是合法子序列

✗ 错误写法：用遍历或二分找前驱

✓ 正确写法：哈希表 O(1) 直接查值→下标

严格递增不代表要二分，哈希查更快更简单

✗ 错误写法：答案忘了「至少 3 个数」

✓ 正确写法：dp 从 2 起算，最终若没接长过就返回 0

长度 2 不算斐波那契，ans 初值 0、只在成功接长时才更新

面试追问把动画讲成自己的话

追问为什么用「末尾两个数」而不是「末尾一个数」定义状态？

斐波那契的下一项由前两项唯一决定，只盯最后一个数无法确定该接什么；固定最后两个数 arr[j]、arr[i]，前驱就被唯一锁成 arr[i] − arr[j]，转移才成立。这也是这类「相邻两项决定下一项」问题的通用建模手法。

追问复杂度还能再优化吗？

主体是枚举 O(n²) 个数对，每对靠哈希 O(1) 查前驱，整体 O(n²) 时间。空间上 dp 表是 O(n²)，可以用哈希表只存有效的 (j,i) 状态来省空间，但时间下界仍是 O(n²)，因为数对本身就有 O(n²) 个。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 动态规划套路 45/108

石子游戏

LeetCode 877 · 中等 · 沿着动态规划套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题