题目描述
思路解析
一句话答案：LeetCode 873 最长的斐波那契子序列的长度：哈希表存每个数的下标，双层循环枚举末尾两数 arr[i]、arr[j]，前驱 arr[i]−arr[j] 若在表里且更靠前，就把这两数结尾的 dp 接长一位。时间、空间均 O(n²)。
最长的斐波那契子序列，到底要在数组里找出什么
给一个严格递增的正整数数组 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²)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「固定末尾两数、往前找前驱 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。
两个高频追问：为何盯末尾两数、复杂度能否再降。
参考代码
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复杂度
- 时间：O(n²)，枚举所有末尾两数对，每对查哈希 O(1)
- 空间：O(n²)，dp 表 n×n，外加 O(n) 哈希表
易错点
面试追问把动画讲成自己的话
追问为什么用「末尾两个数」而不是「末尾一个数」定义状态？
追问复杂度还能再优化吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
石子游戏
LeetCode 877 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题