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