最长斐波那契子序列的长度 题目描述 给定一个严格递增的正整数数组 arr，找到 arr 中最长的斐波那契式子序列的长度。如果一个序列满足以下条件，则称其为斐波那契式序列： len(sequence) >= 3 对于所有 i (i >= 2)，都有 sequence[ i] = sequence[ i-1] + sequence[ i-2 ] 注意：子序列是从原数组中删除一些（或不删除）元素，剩余元素保持原始顺序得到的序列。 示例： 输入：arr = [ 1,2,3,4,5,6,7,8 ] 输出：5 解释：最长的斐波那契式子序列是 [ 1,2,3,5,8] 或 [ 3,5,8,13,21]（但13和21不在数组中，所以是[ 1,2,3,5,8 ]） 解题过程 步骤1：理解问题本质 我们需要找到最长的满足斐波那契关系的序列。关键观察是：斐波那契序列中的每个数都由前两个数唯一确定。如果我们知道序列中的两个连续数 arr[ i] 和 arr[ j]（i < j），那么下一个数必须是 arr[ i] + arr[ j ]。 步骤2：确定状态定义 定义 dp[ i][ j] 表示以 arr[ i] 和 arr[ j] 作为最后两个元素的斐波那契式子序列的最大长度（其中 i < j）。 为什么这样定义？因为斐波那契关系只依赖于最后两个数，知道了最后两个数，我们就能确定整个序列的递推关系。 步骤3：状态转移方程 对于一对索引 (i, j)，我们要找是否存在一个前驱数 arr[ k ]，使得： arr[ k] + arr[ i] = arr[ j] 且 k < i 如果存在这样的 k，那么以 arr[ i] 和 arr[ j] 结尾的序列长度就是 dp[ k][ i ] + 1。 如果不存在这样的 k，那么最小长度就是 2（只有 arr[ i] 和 arr[ j ] 两个数）。 状态转移方程： dp[ i][ j] = max(dp[ i][ j], dp[ k][ i] + 1) if arr[ k] + arr[ i] = arr[ j ] 否则 dp[ i][ j ] = 2 步骤4：初始化和边界情况 所有 dp[ i][ j ] 初始化为 2，因为任意两个数都可以组成长度为 2 的序列。 我们需要一个哈希表来快速查找 arr[ k] = arr[ j] - arr[ i ] 是否存在，以及它的索引。 步骤5：算法实现细节 创建哈希表 value_ to_ index，将数值映射到索引 初始化二维dp数组，大小 n×n，所有值设为 2 双重循环遍历 j 从 1 到 n-1，i 从 0 到 j-1 计算前驱值 prev = arr[ j] - arr[ i ] 如果 prev 存在且索引 k < i，则更新 dp[ i][ j] = dp[ k][ i ] + 1 记录过程中的最大值 步骤6：具体示例演示 以 arr = [ 1,2,3,4,5,6,7,8 ] 为例： 当 j=2, i=1：arr[ i]=2, arr[ j ]=3, prev=1 找到 k=0 (arr[ 0]=1), 且 k < i dp[ 1][ 2] = dp[ 0][ 1 ] + 1 = 2 + 1 = 3 当 j=4, i=3：arr[ i]=4, arr[ j ]=5, prev=1 找到 k=0 (arr[ 0 ]=1), 但 1+4=5≠3? 重新检查... 更完整的计算过程： 序列 [ 1,2,3]：dp[ 1][ 2] = dp[ 0][ 1 ] + 1 = 3 序列 [ 2,3,5]：dp[ 2][ 4] = dp[ 1][ 2 ] + 1 = 4 序列 [ 3,5,8]：dp[ 4][ 7] = dp[ 2][ 4 ] + 1 = 5 步骤7：复杂度分析 时间复杂度：O(n²)，双重循环 空间复杂度：O(n²)，dp数组的大小 步骤8：最终答案处理 最终答案是所有 dp[ i][ j ] 中的最大值，但如果最大值小于 3，说明没有满足条件的斐波那契序列，返回 0。