带限制条件的最长斐波那契式子序列长度

题目描述
给定一个严格递增的正整数数组 A，找出最长的斐波那契式子序列的长度。斐波那契式子序列需满足：对于子序列中任意三个连续元素 X, Y, Z（其中 X < Y < Z），有 X + Y = Z。同时，子序列需至少包含三个元素。若不存在这样的子序列，返回 0。

示例
输入：A = [1, 3, 7, 11, 12, 14, 18]
输出：3
解释：最长斐波那契式子序列为 [1, 11, 12]（因为 1 + 11 = 12），或 [3, 11, 14]（3 + 11 = 14），或 [7, 11, 18]（7 + 11 = 18）。

解题步骤

步骤 1：理解问题本质

斐波那契式子序列的核心是任意相邻三项满足递推关系。若设子序列为 ... , A[i], A[j], A[k] ...，则必须有：

A[i] + A[j] = A[k]

其中 i < j < k 且 A 严格递增。

关键点：

• 子序列不要求连续，但需保持原数组顺序。
• 至少需要三个元素。

步骤 2：定义状态

暴力枚举所有三元组 (i, j, k) 的复杂度为 O(n³)，不可行。我们采用动态规划优化：

定义 dp[j][k] 表示以 A[j] 和 A[k] 作为最后两个元素的斐波那契式子序列的最大长度。

• 若存在 A[i] 满足 A[i] + A[j] = A[k]，则 dp[j][k] = dp[i][j] + 1。
• 若不存在这样的 A[i]，但 A[j] 和 A[k] 可作为起点，则 dp[j][k] = 2（表示只有两个元素，但最终有效序列需长度 ≥3，因此需忽略）。

目标：遍历所有 j < k，计算 dp[j][k]，并记录最大值。

步骤 3：状态转移方程

对于固定的 j 和 k，我们需要查找是否存在 A[i] = A[k] - A[j]：

1. 若 A[i] 存在且 i < j，则 dp[j][k] = dp[i][j] + 1。
2. 若 A[i] 不存在，则 dp[j][k] = 2（初始状态）。

注意：由于数组严格递增，可用哈希表记录每个值的索引，快速查找 A[i]。

步骤 4：具体执行流程

1. 初始化哈希表 valToIndex，记录每个值对应的索引。
2. 初始化 dp 为二维数组（全填 2），因为任意两个数可视为长度为 2 的序列。
3. 遍历 j 从 0 到 n-2，遍历 k 从 j+1 到 n-1：
   • 计算 prev = A[k] - A[j]。
   • 若 prev 在哈希表中且索引 i 满足 i < j，则更新 dp[j][k] = dp[i][j] + 1。
4. 遍历过程中记录最大长度 maxLen，若 maxLen ≥ 3 则返回 maxLen，否则返回 0。

步骤 5：示例推导

以 A = [1, 3, 7, 11, 12, 14, 18] 为例：

• j=0, k=3：A[j]=1, A[k]=11 → prev=10（不存在） → dp[0][3]=2。
• j=1, k=3：A[j]=3, A[k]=11 → prev=8（不存在） → dp[1][3]=2。
• j=0, k=4：A[j]=1, A[k]=12 → prev=11（存在，索引 3）但 3 > j=0，不满足 i<j，故 dp[0][4]=2。
• 关键情况：j=3, k=4：A[j]=11, A[k]=12 → prev=1（存在，索引 0）且 0 < j=3 → dp[3][4] = dp[0][3] + 1 = 2 + 1 = 3。
  此时得到序列 [1, 11, 12]，长度为 3。

继续遍历可发现 [3,11,14] 和 [7,11,18] 也满足条件。

步骤 6：复杂度分析

• 时间复杂度：O(n²)，因需遍历所有 (j, k) 对。
• 空间复杂度：O(n²) 用于存储 dp 数组，哈希表 O(n)。

步骤 7：代码实现（伪代码）

function lenLongestFibSubseq(A):
    n = len(A)
    valToIndex = {A[i]: i for i in range(n)}
    dp = [[2] * n for _ in range(n)]
    maxLen = 0
    
    for j in range(n):
        for k in range(j+1, n):
            prev = A[k] - A[j]
            if prev in valToIndex and valToIndex[prev] < j:
                i = valToIndex[prev]
                dp[j][k] = dp[i][j] + 1
                maxLen = max(maxLen, dp[j][k])
    
    return maxLen if maxLen >= 3 else 0

总结
本题通过动态规划将问题转化为“以每对元素为结尾”的子序列长度计算，利用哈希表快速查找前驱元素，避免了三重循环。关键在于理解状态定义和递推关系。