难度：★★★☆☆
类型：数组
方法：数学

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。
示例 2：

输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。

提示：

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
（对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）

解答

我们使用动态两种方法解决这个问题。

方案1：直接了当

有一个重要的定理：一旦斐波那契数列的最开始两个数字确定了，那么整个数列就确定了。

官网解答就是根据这个定理，我们先通过两层循环找到两个数字，然后一一统计以这两个数字为开始的斐波那契数列的长度，选择最大值即可。这里通过while循环获得这个最大长度。另外有一个技巧就是通过python中的集合来加速元素搜寻。

class Solution(object):
    def lenLongestFibSubseq(self, A):
        S = set(A)
        ans = 0
        for i in (len(A)):
            for j in range(i+1, len(A)):
                x, y = A[j], A[i] + A[j]
                length = 2
                while y in S:
                    x, y = y, x + y
                    length += 1
                ans = max(ans, length)
        return ans if ans >= 3 else 0

方案2: 动态规划

我们假设连起来的三个元素，斐波那契三元组分别为num_1，num_2，num_3，num_1+num_2=num_3

【数组定义】定义数组dp，这里我们用字典来表示，字典的键是(num_2，num_3)组成的元组，字典的值是以num_2和num_3结尾的斐波那契数列的长度。

【初始状态】两个数字不能组成斐波那契数列，但是已经包含了长度为2。

【递推公式】这次我们首先寻找较大的两个数字num_2和num_3，然后通过减法计算获得num_1，组成斐波那契三元组，如果这个最小的数字num_1超过了num_2或者不在数组中，我们一概不能考虑的，只有当这个数字满足条件时，我们才进行递归计算：

元组(num_1, num_2)在dp字典中，将该元组对应的值也就是以(num_1, num_2)结尾的斐波那契数列长度+1，赋值给(num_2, num_3)位置处。

元组(num_1, num_2)不在字典中，说明没有以(num_1, num_2)结尾的斐波那契数列，直接将3赋值给(num_2, num_3)位置。

同时需要及时更新最长斐波那契数列变量res。

【返回值】

最终返回res即可。

class Solution:
    def lenLongestFibSubseq(self, A) -> int:

        dp = dict()
        res = 0
        array = set(A)
        for index_3 in range(1, len(A)):
            for index_2 in range(index_3):
                num_2, num_3 = A[index_2], A[index_3]
                num_1 = num_3 - num_2                   # 假想出来的
                if num_1 < num_2 and num_1 in array:
                    length = 3 if (num_1, num_2) not in dp else dp[(num_1, num_2)] + 1
                    res = max(res, length)
                    dp[(num_2, num_3)] = length

        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析