带有限制条件的最长斐波那契子序列（长度至少为3） 题目描述 给定一个严格递增的正整数数组 arr ，请你找出并返回满足以下条件的斐波那契式 子序列 的最大长度（子序列的长度至少为3）： 子序列中的任意两个相邻项之和等于后一项。 子序列是原数组的子序列（不要求连续）。 子序列中任意三项的值必须满足严格递增关系。 如果不存在这样的斐波那契式子序列，则返回 0。 示例 输入：arr = [ 1, 2, 3, 4, 5, 6, 7, 8 ] 输出：5 解释：最长的斐波那契式子序列为 [ 1, 2, 3, 5, 8 ]，满足相邻两项之和等于后一项。 解题思路 斐波那契式子序列的定义类似于斐波那契数列：对于序列中的任意连续三项 x, y, z ，应满足 x + y = z 。 由于数组是严格递增的，我们可以利用动态规划来记录以任意两个元素作为最后两项时，能够形成的斐波那契子序列的最大长度。 步骤拆解 状态定义 我们定义 dp[j][i] 表示以 arr[j] 和 arr[i] 作为斐波那契子序列的最后两项时，该子序列的最大长度（长度至少为2，因为包含了最后两项）。 如果存在前一项 arr[k] 满足 arr[k] + arr[j] = arr[i] ，那么 dp[j][i] = dp[k][j] + 1 。 否则， dp[j][i] 的默认值为 2（仅包含最后两项）。 状态转移 对于每个 i （作为当前最后一项的索引），我们遍历所有可能的 j （倒数第二项），然后寻找是否存在 k 使得： arr[k] + arr[j] = arr[i] 由于数组是严格递增的，我们可以用双指针法或哈希表来快速查找这样的 k 。 如果找到 k ，则更新 dp[j][i] = dp[k][j] + 1 ；否则 dp[j][i] = 2 。 边界条件 所有 dp[j][i] 初始化为 2，因为至少包含 arr[j] 和 arr[i] 两项。 当 dp[j][i] >= 3 时，我们更新全局最大长度。 查找前一项 arr[k] 的方法 由于数组严格递增，可以使用哈希表记录每个值的索引，这样对于给定的 arr[j] 和 arr[i] ，我们可以计算 target = arr[i] - arr[j] ，并在哈希表中查找 target 是否存在且索引 k < j 。 如果存在，则 k 就是前一项的索引。 最终答案 遍历所有 i 和 j （ j < i ），记录 dp[j][i] 的最大值，如果最大值小于 3 则返回 0，否则返回最大值。 详细过程 假设 arr = [1, 2, 3, 4, 5, 6, 7, 8] ，我们逐步计算： 建立哈希表 value_to_index ，例如 1:0, 2:1, 3:2, ... 。 初始化 dp 为二维数组，大小 n x n ，全部初始化为 2。 从 i = 2 到 n-1 （因为最后一项至少是第三项）： 对于每个 j 从 0 到 i-1 ： 计算 target = arr[i] - arr[j] 。 如果 target 在哈希表中且索引 k < j ： dp[j][i] = dp[k][j] + 1 。 更新全局最大长度 max_len = max(max_len, dp[j][i]) 。 最终 max_len = 5 ，对应序列 [1, 2, 3, 5, 8] 。 时间复杂度 双重循环遍历 i 和 j ，复杂度为 O(n²)。 哈希表查找为 O(1)，因此总时间复杂度为 O(n²)。 空间复杂度为 O(n²) 用于存储 dp 表。 关键点 状态定义要抓住“最后两项”这个关键，因为斐波那契关系由连续三项决定。 利用哈希表可以快速找到满足条件的前一项，避免了三重循环。 最终答案要判断长度是否至少为 3，否则返回 0。 这样，我们就得到了一个高效求解最长斐波那契子序列的线性动态规划解法。