最长斐波那契子序列的长度 题目描述 给定一个严格递增的正整数数组 arr，你需要找出数组中最长的斐波那契式子序列的长度。如果一个序列满足以下条件，则称其为斐波那契式子序列： 序列长度 >= 3 对于所有满足 i+2 < 序列长度 的 i，都有 X_ i + X_ {i+1} = X_ {i+2} 例如，对于数组 arr = [ 1, 2, 3, 4, 5, 6, 7, 8 ]： 最长的斐波那契子序列之一是 [ 3, 5, 8 ]，因为 3+5=8。 另一个是 [ 1, 2, 3, 5, 8 ]，因为 1+2=3, 2+3=5, 3+5=8，其长度为 5。 你的任务是找出并返回最长斐波那契子序列的长度。如果不存在这样的序列，返回 0。 解题过程 第一步：理解问题核心 斐波那契子序列的关键特征是：每个元素（从第三个开始）都是前两个元素之和。由于数组是严格递增的，我们可以利用这个特性来设计算法。 第二步：暴力枚举思路（不可行但有助于理解） 最直接的思路是枚举所有可能的前两个元素 (arr[ i], arr[ j])，然后检查是否存在 arr[ i] + arr[ j]，如果存在，就继续检查 arr[ j] + (arr[ i]+arr[ j ])，以此类推。但这种方法的时间复杂度是 O(n^3)，对于较大的数组会超时。 第三步：动态规划状态定义 我们需要一个高效的方法来记录信息。定义 dp[ j][ k] 表示以 arr[ j] 和 arr[ k ] 作为最后两个元素的斐波那契子序列的最大长度。 为什么这样定义？因为斐波那契序列由最后两个数唯一确定。如果我们知道最后两个数是 arr[ j] 和 arr[ k]，那么前一个数一定是 arr[ k] - arr[ j]（记为 arr[ i]），序列长度就是 dp[ i][ j ] + 1。 第四步：状态转移方程 对于一对索引 (j, k)，其中 j < k： 计算前一个数：prev = arr[ k] - arr[ j ] 如果 prev 存在于数组中，并且 prev < arr[ j]（保证顺序），设 prev = arr[ i ]，那么状态转移方程为： dp[ j][ k] = dp[ i][ j ] + 1 如果 prev 不存在或者 prev >= arr[ j]，那么无法形成更长的序列，dp[ j][ k ] = 2（基础长度，表示只有两个数） 第五步：初始化 初始时，任意两个数都可以视为一个长度为 2 的"基础"斐波那契序列。因此，所有 dp[ j][ k ] 的初始值都是 2。 第六步：算法实现步骤 创建一个哈希表，记录每个数值对应的索引，便于快速查找 prev = arr[ k] - arr[ j ] 的位置 i。 初始化一个二维数组 dp，大小为 n×n，所有值设为 2。 使用双重循环遍历所有 j 和 k（j < k）： 计算 prev = arr[ k] - arr[ j ] 如果 prev 存在于哈希表中，且其索引 i < j： 更新 dp[ j][ k] = dp[ i][ j ] + 1 遍历所有 dp[ j][ k ]，找出最大值 maxLen。 如果 maxLen > 2，返回 maxLen；否则返回 0。 第七步：示例演示 以 arr = [ 1, 2, 3, 4, 5, 6, 7, 8 ] 为例： 当 j=0, k=1 (值1,2)：prev=2-1=1，存在且i=0<1，dp[ 0][ 1]=dp[ 0][ 0]+1? 不对，因为i=0,j=0? 这里需要检查 i < j。实际上 prev=1 对应 i=0，但 j=0，i 不满足 i<j。所以 dp[ 0][ 1 ]=2。 当 j=1, k=2 (值2,3)：prev=3-2=1，存在且i=0<1，dp[ 1][ 2]=dp[ 0][ 1 ]+1=3。 当 j=2, k=3 (值3,4)：prev=1，不存在于数组中，dp[ 2][ 3 ]=2。 当 j=2, k=4 (值3,5)：prev=2，存在且i=1<2，dp[ 2][ 4]=dp[ 1][ 2 ]+1=4。 继续这个过程，最终会找到 dp[ 4][ 7]（对应值5,8）：prev=3，存在且i=2<4，dp[ 4][ 7]=dp[ 2][ 4 ]+1=5。 最终找到最长斐波那契子序列长度为 5。 第八步：复杂度分析 时间复杂度：O(n²)，因为需要双重循环遍历所有数对。 空间复杂度：O(n²)，用于存储 dp 数组。 这个算法通过动态规划巧妙地利用了斐波那契序列的特性，高效地解决了问题。