最长斐波那契子序列的长度 题目描述 给定一个严格递增的正整数数组 arr，找到 arr 中最长的斐波那契式子序列的长度。如果一个序列满足以下条件，则称为斐波那契式序列： 对于每个 i（i ≥ 2），都有 X_ i = X_ {i-1} + X_ {i-2}。 例如，arr = [ 1,2,3,4,5,6,7,8] 的最长斐波那契式子序列之一是 [ 1,2,3,5,8 ]，长度为 5。 解题过程 问题分析 斐波那契式子序列由任意两个起始元素确定，后续每个元素是前两个元素之和。由于数组严格递增，我们可以利用动态规划记录以每对元素结尾的最长序列长度。 状态定义 定义 dp[ j][ i] 表示以 arr[ j] 和 arr[ i] 作为最后两个元素的斐波那契式子序列的最大长度（j < i）。如果存在前一个元素 arr[ k] 满足 arr[ k] + arr[ j] = arr[ i]，则状态转移为 dp[ j][ i] = dp[ k][ j ] + 1。 初始状态 任意两个元素至少可以构成长度为 2 的序列，因此初始时所有 dp[ j][ i ] = 2。 寻找前驱元素 对于固定的 j 和 i，需要快速查找是否存在 arr[ k] = arr[ i] - arr[ j] 且 k < j。由于数组严格递增，可以用哈希表记录每个元素的值到索引的映射，实现 O(1) 查找。 状态转移方程 计算差值 diff = arr[ i] - arr[ j ]。 若哈希表中存在 diff 且其索引 k < j，则 dp[ j][ i] = dp[ k][ j ] + 1。 否则保持 dp[ j][ i ] = 2。 同时更新全局最大长度 max_ len。 示例推演 以 arr = [ 1,2,3,4,5,6,7,8 ] 为例： 初始化哈希表：{1:0, 2:1, 3:2, 4:3, 5:4, 6:5, 7:6, 8:7}。 遍历 j=1, i=2：arr[ j]=2, arr[ i]=3，diff=1，存在 k=0，dp[ 1][ 2]=dp[ 0][ 1]+1=3（序列 [ 1,2,3 ]）。 遍历 j=2, i=3：arr[ j]=3, arr[ i]=4，diff=1，但 k=0 < j=2，但 arr[ 0]=1, arr[ 2 ]=3，1+3=4≠5，无效。 继续遍历，最终找到序列 [ 1,2,3,5,8] 对应 dp[ 4][ 7 ]=5。 复杂度分析 时间复杂度：O(n²)，需要双重循环遍历 j 和 i。 空间复杂度：O(n²)，用于存储 dp 数组。 边界情况 数组长度小于 3 时直接返回 0。 若所有序列长度均不超过 2，返回 0（题目要求斐波那契序列长度至少为 3）。 通过以上步骤，即可高效求解最长斐波那契子序列的长度。