文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 暴力解
    • 2.2 動態(tài)規(guī)劃

1. 題目

如果序列 X_1, X_2, ..., X_n 滿足下列條件，就說它是 斐波那契式 的：

• $n>=3$
• 對于所有 $i+2<=n$，都有 $X_i+X_{i+1}=X_{i+2}$

給定一個嚴(yán)格遞增的正整數(shù)數(shù)組形成序列，找到 A 中最長的斐波那契式的子序列的長度。如果一個不存在，返回 0 。

（回想一下，子序列是從原序列 A 中派生出來的，它從 A 中刪掉任意數(shù)量的元素（也可以不刪），而不改變其余元素的順序。例如， [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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

2.1 暴力解

• 以兩個點(diǎn)為基準(zhǔn)，生成斐波那契數(shù)列，在set中查找是否找到生成的數(shù)，記錄最大 len
• 時間復(fù)雜度 $O(n^2{\log }_{2}n)$

class Solution { public:int lenLongestFibSubseq(vector<int>& A) {unordered_set<int> s;for(int Ai : A)s.insert(Ai);int a, b, c, len = 0, maxlen = 0;for(int i = 0, j; i < A.size(); ++i){for(j = i+1; j < A.size(); ++j){len = 2;c = A[i]+A[j];a = A[i];b = A[j];while(s.count(c)){len++;maxlen = max(maxlen, len);a = b;b = c;c = a+b;}}}return maxlen;} };

384 ms 9 MB

2.2 動態(tài)規(guī)劃

• dp[i][j] 表示以 A[i],A[j]結(jié)尾的序列長度
• 初始化所有可能的dp[i][j] = 2, i < j
• 預(yù)先將A的數(shù)值和 idx 插入哈希map，方便后面查找
• 對于 i, j 結(jié)尾的序列，其前一位數(shù)應(yīng)該是 A[j]-A[i]，查找其是否存在與哈希表中
• 如果存在，且其 idx < idx_i ，可以把前面的A[idx],A[i]結(jié)尾的序列跟 A[j]組成更長的序列，則 dp[i][j] = max(dp[i][j],dp[idx][i]+1)

class Solution { public:int lenLongestFibSubseq(vector<int>& A) {unordered_map<int,int> m;//val, idxint i, j, prevAi, idx, maxlen = 0, n = A.size();for(i = 0; i < n; ++i)m[A[i]] = i;vector<vector<int>> dp(n,vector<int>(n,0));//dp[i][j] 表示以 A[i],A[j]結(jié)尾的序列長度for(i = 0; i < n; ++i)for(j = i+1; j < n; ++j)dp[i][j] = 2;for(i = 0; i < A.size(); ++i){for(j = i+1; j < A.size(); ++j){prevAi = A[j]-A[i];//A[i] 前一位數(shù)if(m.count(prevAi)){idx = m[prevAi];//前一位數(shù)下標(biāo)if(idx < i)//在 i 前面{dp[i][j] = max(dp[i][j],dp[idx][i]+1);//更長的序列maxlen = max(maxlen,dp[i][j]);}}}}return maxlen;} };

416 ms 61.9 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 873. 最长的斐波那契子序列的长度（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。