本文共 2498 字，大约阅读时间需要 8 分钟。

1. 题目

如果序列 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 <= 10001 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 暴力解

• 以两个点为基准，生成斐波那契数列，在set中查找是否找到生成的数，记录最大 len
• 时间复杂度 $O(n^2{\log }_{2}n)$

class Solution {
   public:    int lenLongestFibSubseq(vector
   
    & A) {
       	unordered_set
    
      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 动态规划

• dp[i][j] 表示以 A[i],A[j]结尾的序列长度
• 初始化所有可能的dp[i][j] = 2, i < j
• 预先将A的数值和 idx 插入哈希map，方便后面查找
• 对于 i, j 结尾的序列，其前一位数应该是 A[j]-A[i]，查找其是否存在与哈希表中
• 如果存在，且其 idx < idx_i ，可以把前面的A[idx],A[i]结尾的序列跟 A[j]组成更长的序列，则 dp[i][j] = max(dp[i][j],dp[idx][i]+1)

class Solution {
   public:    int lenLongestFibSubseq(vector
   
    & A) {
       	unordered_map
    
      m;//val, idx        int i, j, prevAi, idx, maxlen = 0, n = A.size();    	for(i = 0; i < n; ++i)    		m[A[i]] = i;    	vector
     
      
       > dp(n,vector
       
        (n,0));    	//dp[i][j] 表示以 A[i],A[j]结尾的序列长度    	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] 前一位数                if(m.count(prevAi))                {
                   	idx = m[prevAi];//前一位数下标                	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

转载地址：https://michael.blog.csdn.net/article/details/105821793 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！