難度：★★★☆☆
類型：數(shù)組
方法：數(shù)學(xué)
力扣鏈接請(qǐng)移步本題傳送門
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄
題目
如果序列 X_1, X_2, ..., X_n 滿足下列條件，就說它是 斐波那契式 的：
n >= 3
對(duì)于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
給定一個(gè)嚴(yán)格遞增的正整數(shù)數(shù)組形成序列蛙吏，找到 A 中最長(zhǎng)的斐波那契式的子序列的長(zhǎng)度。如果一個(gè)不存在厘线，返回 0 。
（回想一下出革，子序列是從原序列 A 中派生出來的造壮，它從 A 中刪掉任意數(shù)量的元素（也可以不刪），而不改變其余元素的順序骂束。例如耳璧， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一個(gè)子序列）
示例 1：
輸入: [1,2,3,4,5,6,7,8]
輸出: 5
解釋:
最長(zhǎng)的斐波那契式子序列為：[1,2,3,5,8] 硝全。
示例 2：
輸入: [1,3,7,11,12,14,18]
輸出: 3
解釋:
最長(zhǎng)的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 楞抡。
提示：
3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
（對(duì)于以 Java，C析藕，C++召廷，以及 C# 的提交，時(shí)間限制被減少了 50%）
解答
我們使用動(dòng)態(tài)兩種方法解決這個(gè)問題账胧。
方案1：直接了當(dāng)
有一個(gè)重要的定理：一旦斐波那契數(shù)列的最開始兩個(gè)數(shù)字確定了竞慢，那么整個(gè)數(shù)列就確定了。
官網(wǎng)解答就是根據(jù)這個(gè)定理治泥，我們先通過兩層循環(huán)找到兩個(gè)數(shù)字筹煮，然后一一統(tǒng)計(jì)以這兩個(gè)數(shù)字為開始的斐波那契數(shù)列的長(zhǎng)度，選擇最大值即可居夹。這里通過while循環(huán)獲得這個(gè)最大長(zhǎng)度败潦。另外有一個(gè)技巧就是通過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: 動(dòng)態(tài)規(guī)劃
我們假設(shè)連起來的三個(gè)元素准脂，斐波那契三元組分別為num_1劫扒，num_2，num_3狸膏，num_1+num_2=num_3
【數(shù)組定義】定義數(shù)組dp沟饥，這里我們用字典來表示，字典的鍵是(num_2湾戳，num_3)組成的元組贤旷，字典的值是以num_2和num_3結(jié)尾的斐波那契數(shù)列的長(zhǎng)度。
【初始狀態(tài)】?jī)蓚€(gè)數(shù)字不能組成斐波那契數(shù)列砾脑，但是已經(jīng)包含了長(zhǎng)度為2幼驶。
【遞推公式】這次我們首先尋找較大的兩個(gè)數(shù)字num_2和num_3，然后通過減法計(jì)算獲得num_1拦止，組成斐波那契三元組县遣，如果這個(gè)最小的數(shù)字num_1超過了num_2或者不在數(shù)組中，我們一概不能考慮的汹族，只有當(dāng)這個(gè)數(shù)字滿足條件時(shí)萧求，我們才進(jìn)行遞歸計(jì)算：
元組(num_1, num_2)在dp字典中，將該元組對(duì)應(yīng)的值也就是以(num_1, num_2)結(jié)尾的斐波那契數(shù)列長(zhǎng)度+1顶瞒，賦值給(num_2, num_3)位置處夸政。
元組(num_1, num_2)不在字典中，說明沒有以(num_1, num_2)結(jié)尾的斐波那契數(shù)列榴徐，直接將3賦值給(num_2, num_3)位置守问。
同時(shí)需要及時(shí)更新最長(zhǎng)斐波那契數(shù)列變量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
如有疑問或建議耗帕，歡迎評(píng)論區(qū)留言~
有關(guān)更多力扣中等題的python解決方案穆端，請(qǐng)移步力扣中等題解析
