带限制条件的最长斐波那契子序列 题目描述 给定一个严格递增的正整数数组 arr ，找出数组中最长的斐波那契式子序列的长度。斐波那契式子序列需满足：对于所有 i ≥ 2 ，有 X_i = X_{i-1} + X_{i-2} 。注意：子序列不要求连续，但必须保持原数组中的相对顺序。如果不存在这样的子序列，返回 0。 示例 输入：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：理解斐波那契子序列的定义 斐波那契子序列需满足递推关系：对于任意三个连续元素 a, b, c （在子序列中连续出现），必须有 c = a + b 。由于数组严格递增，可以通过两个起始元素唯一确定一个斐波那契序列。 关键点 ： 子序列不要求连续，但元素顺序必须与原数组一致。 斐波那契序列由前两个元素唯一确定。 我们需要找到最长的满足条件的子序列。 步骤2：定义状态 使用动态规划，定义状态： dp[i][j] 表示以 arr[i] 和 arr[j] 作为斐波那契子序列最后两个元素时的最大长度（其中 i < j ）。 为什么这样定义？ 因为斐波那契序列由最后两个元素决定：如果存在前一个元素 arr[k] 满足 arr[k] + arr[i] = arr[j] ，则可以将 arr[k] 加入序列，长度加1。 步骤3：状态转移方程 对于固定的 j ，遍历所有 i < j ，检查是否存在 k 满足： k < i arr[k] + arr[i] = arr[j] 如果存在这样的 k ，则状态转移为： dp[i][j] = dp[k][i] + 1 否则， dp[i][j] 的初始长度为 2（仅包含 arr[i] 和 arr[j] 两个元素）。 注意 ：需要确保 arr[k] 存在于数组中。由于数组严格递增，可以用哈希表快速查找 arr[k] = arr[j] - arr[i] 是否存在。 步骤4：初始化 所有 dp[i][j] 的初始值默认为 2，因为任意两个元素都可以视为一个长度为2的斐波那契子序列的起点。 步骤5：算法实现细节 创建一个哈希表 indexMap ，记录每个元素的值到其下标的映射，用于快速查找 arr[k] 。 遍历 j 从 2 到 n-1，对于每个 j ，遍历 i 从 1 到 j-1： 计算 prev = arr[j] - arr[i] 如果 prev < arr[i] 且 prev 存在于数组中（设下标为 k ），则更新： dp[i][j] = dp[k][i] + 1 在遍历过程中记录最大的 dp[i][j] 。 步骤6：示例推导（arr = [ 1,2,3,4,5,6,7,8]） 初始化：所有 dp[i][j] = 2 。 当 j=2 （元素3）， i=1 （元素2）： prev = 3-2 = 1 ，存在且下标 k=0 ， 1<2 满足条件。 dp[1][2] = dp[0][1] + 1 = 2 + 1 = 3 （序列 [ 1,2,3 ]）。 当 j=4 （元素5）， i=3 （元素4）： prev = 5-4=1 ，但 1<4 不成立（因为1<4但需要检查k是否存在），实际 k=0 存在，但 dp[0][3] 未定义？注意：必须确保 k < i 。这里 k=0 < i=3 成立，但 dp[0][3] 初始为2，所以 dp[3][4]=3 （序列 [ 1,4,5] 无效？因为1和4不连续）。实际上，需要前两个元素连续在子序列中。正确序列应为 [ 1,2,3,5,8 ] 的推导： 对于 j=4 （元素5）， i=2 （元素3）： prev=2 ，存在且 k=1 ， dp[2][4] = dp[1][2] + 1 = 3+1=4 （序列 [ 1,2,3,5 ]）。 继续推导可得最长长度为5。 步骤7：复杂度分析 时间复杂度：O(n²)，需要两层循环遍历 i 和 j 。 空间复杂度：O(n²)，用于存储 dp 数组。 总结 本题通过动态规划记录以每对元素为结尾的斐波那契子序列长度，利用哈希表快速查找前驱元素，逐步扩展序列长度。最终遍历所有状态得到最大值。