LeetCode 873中等动态规划
最长的斐波那契子序列的长度 图解题解
这道题到底在问什么
严格递增数组 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]）
先想最直接的笨办法
开局：左边是严格递增的数组，右边哈希表记录每个「值 → 下标」。接下来枚举末尾两个数 arr[j]（中间数，蓝指针）和 arr[i]（末尾数，紫指针），j 在 i 前面，逐对找前驱。（动画第 4 步）
最优解：一步一步想明白
- 3记住这套「固定末尾两数、往前找前驱 t = arr[i] − arr[j]、查哈希接长一位」，下面每一帧都在套它。
- 4开局：左边是严格递增的数组，右边哈希表记录每个「值 → 下标」。接下来枚举末尾两个数 arr[j]（中间数，蓝指针）和 arr[i]（末尾数，紫指针），j 在 i 前面，逐对找前驱。
- 5固定中间数 arr[1]=2（蓝）和末尾数 arr[2]=3（紫）。要在它们前面接一个数，必须满足 前驱 + 2 = 3，所以前驱 t = 3 − 2 = 1。去哈希表查 1 在不在。
- 6哈希里命中 1，它在下标 0（绿），而且 0 排在 1 前面，顺序合法。于是把以 (1,2) 结尾的那段长度 2 接长一位：dp(2,3) = 3。比旧的最长还长，ans 刷新成 3。
- 7固定中间数 arr[1]=2（蓝）和末尾数 arr[3]=4（紫）。要在它们前面接一个数，必须满足 前驱 + 2 = 4，所以前驱 t = 4 − 2 = 2。去哈希表查 2 在不在。
- 8哈希里虽然有 2，但它在下标 1（红），并不排在中间数 arr[1] 的前面，凑不成「t, 2, 4」这种从左到右的合法顺序，这对作废，dp 保持长度 2。
- 9固定中间数 arr[2]=3（蓝）和末尾数 arr[3]=4（紫）。要在它们前面接一个数，必须满足 前驱 + 3 = 4，所以前驱 t = 4 − 3 = 1。去哈希表查 1 在不在。
- 10哈希里命中 1，它在下标 0（绿），而且 0 排在 2 前面，顺序合法。于是把以 (1,3) 结尾的那段长度 2 接长一位：dp(3,4) = 3。没超过当前最长 ans=3，ans 不变。
- 11固定中间数 arr[1]=2（蓝）和末尾数 arr[4]=5（紫）。要在它们前面接一个数，必须满足 前驱 + 2 = 5，所以前驱 t = 5 − 2 = 3。去哈希表查 3 在不在。
- 12哈希里虽然有 3，但它在下标 2（红），并不排在中间数 arr[1] 的前面，凑不成「t, 2, 5」这种从左到右的合法顺序，这对作废，dp 保持长度 2。
- 13固定中间数 arr[2]=3（蓝）和末尾数 arr[4]=5（紫）。要在它们前面接一个数，必须满足 前驱 + 3 = 5，所以前驱 t = 5 − 3 = 2。去哈希表查 2 在不在。
- 14哈希里命中 2，它在下标 1（绿），而且 1 排在 2 前面，顺序合法。于是把以 (2,3) 结尾的那段长度 3 接长一位：dp(3,5) = 4。比旧的最长还长，ans 刷新成 4。
- 15固定中间数 arr[3]=4（蓝）和末尾数 arr[4]=5（紫）。要在它们前面接一个数，必须满足 前驱 + 4 = 5，所以前驱 t = 5 − 4 = 1。去哈希表查 1 在不在。
- 16哈希里命中 1，它在下标 0（绿），而且 0 排在 3 前面，顺序合法。于是把以 (1,4) 结尾的那段长度 2 接长一位：dp(4,5) = 3。没超过当前最长 ans=4，ans 不变。
- 17固定中间数 arr[1]=2（蓝）和末尾数 arr[5]=8（紫）。要在它们前面接一个数，必须满足 前驱 + 2 = 8，所以前驱 t = 8 − 2 = 6。去哈希表查 6 在不在。
- 18去哈希表查 6，整个数组里根本没有这个数，说明 2 和 8 前面接不上合法的前驱，这一对只能停在长度 2。
- 19固定中间数 arr[2]=3（蓝）和末尾数 arr[5]=8（紫）。要在它们前面接一个数，必须满足 前驱 + 3 = 8，所以前驱 t = 8 − 3 = 5。去哈希表查 5 在不在。
- 20哈希里虽然有 5，但它在下标 4（红），并不排在中间数 arr[2] 的前面，凑不成「t, 3, 8」这种从左到右的合法顺序，这对作废，dp 保持长度 2。
- 21固定中间数 arr[3]=4（蓝）和末尾数 arr[5]=8（紫）。要在它们前面接一个数，必须满足 前驱 + 4 = 8，所以前驱 t = 8 − 4 = 4。去哈希表查 4 在不在。
- 22哈希里虽然有 4，但它在下标 3（红），并不排在中间数 arr[3] 的前面，凑不成「t, 4, 8」这种从左到右的合法顺序，这对作废，dp 保持长度 2。
- 23固定中间数 arr[4]=5（蓝）和末尾数 arr[5]=8（紫）。要在它们前面接一个数，必须满足 前驱 + 5 = 8，所以前驱 t = 8 − 5 = 3。去哈希表查 3 在不在。
- 24哈希里命中 3，它在下标 2（绿），而且 2 排在 4 前面，顺序合法。于是把以 (3,5) 结尾的那段长度 4 接长一位：dp(5,8) = 5。比旧的最长还长，ans 刷新成 5。
- 25枚举完所有末尾两数对，最长的一条是绿色这 5 个：1、2、3、5、8。它们环环相扣，1+2=3、2+3=5、3+5=8，正好是斐波那契式，答案就是 5。灰掉的 4 没被选进这条链。
⚠️ 容易写错的地方
✗ 错：前驱下标 k 不要求在 j 前面
✓ 对：必须 k 在 j 前面（k 小于 j）
三个数下标要从左到右严格递增，才是合法子序列
✗ 错：用遍历或二分找前驱
✓ 对：哈希表 O(1) 直接查值→下标
严格递增不代表要二分，哈希查更快更简单
✗ 错：答案忘了「至少 3 个数」
✓ 对：dp 从 2 起算，最终若没接长过就返回 0
长度 2 不算斐波那契，ans 初值 0、只在成功接长时才更新
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
O(n²)
枚举所有末尾两数对，每对查哈希 O(1)
空间
O(n²)
dp 表 n×n，外加 O(n) 哈希表
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最长的斐波那契子序列的长度 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用「末尾两个数」而不是「末尾一个数」定义状态？+
斐波那契的下一项由前两项唯一决定，只盯最后一个数无法确定该接什么；固定最后两个数 arr[j]、arr[i]，前驱就被唯一锁成 arr[i] − arr[j]，转移才成立。这也是这类「相邻两项决定下一项」问题的通用建模手法。
复杂度还能再优化吗？+
主体是枚举 O(n²) 个数对，每对靠哈希 O(1) 查前驱，整体 O(n²) 时间。空间上 dp 表是 O(n²)，可以用哈希表只存有效的 (j,i) 状态来省空间，但时间下界仍是 O(n²)，因为数对本身就有 O(n²) 个。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最长的斐波那契子序列的长度 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。