C ++中最长斐波那契子序列的长度
假设我们有一个序列X_1,X_2,...,X_n如斐波那契式-
n>=3
所有i+2<=n的X_i+X_{i+1}=X_{i+2}
现在假设一个正整数的数组A严格增加,形成一个序列,我们必须找到A的最长斐波那契式子序列的长度。如果一个不存在,则返回0。因此,如果该数字类似于[1,2,3,4,5,6,7,8],则输出将为5。最长的子序列是Fibonacci,就像[1,2,3,5,8]。
为了解决这个问题,我们将遵循以下步骤-
ret:=0
创建一个映射m,n:=数组A的大小
创建一个大小为nxn的称为dp的矩阵
对于i,范围为0至n–1
req:=A[i]–A[j]
当A[i]–A[j]<A[j]并且m具有(A[i]–A[j])时,
否则dp[i,j]:=dp[i,j]和2的最大值
ret:=ret和dp[i,j]的最大值
dp[i,j]:=dp[i,j]的最大值,dp[j,m[A[i]–A[j]]]+1
m[A[i]]:=i
对于范围i–1中的j,降低到0
当ret>=3时返回ret,否则返回0。
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h> using namespace std; class Solution { public: int lenLongestFibSubseq(vector<int> & A) { int ret = 0; unordered_map <int, int> m; int n = A.size(); vector < vector <int> > dp(n, vector <int>(n)); for(int i = 0; i < n; i++){ m[A[i]] = i; for(int j = i - 1; j >= 0; j--){ int req = A[i] - A[j]; if(A[i] - A[j] < A[j] && m.count(A[i] - A[j])){ dp[i][j] = max(dp[i][j], dp[j][m[A[i] - A[j]]] + 1); }else{ dp[i][j] = max(dp[i][j], 2); } ret = max(ret, dp[i][j]); } } return ret >= 3 ? ret : 0; } }; main(){ vector<int> v = {1,2,3,4,5,6,7,8}; Solution ob; cout << (ob.lenLongestFibSubseq(v)); }
输入项
[1,2,3,4,5,6,7,8]
输出结果
5