难度：★★★☆☆
类型：数组
方法：数学
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
题目
如果序列 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解决方案，请移步力扣中等题解析
