Giả sử chúng ta có một chuỗi X_1, X_2, ..., X_n giống fibonacci nếu -
-
n> =3
-
X_i + X_ {i + 1} =X_ {i + 2} cho tất cả i + 2 <=n
Bây giờ, giả sử một dãy A tăng dần các số nguyên dương tạo thành một dãy, chúng ta phải tìm độ dài của dãy con giống fibonacci dài nhất của A. Nếu không tồn tại, thì trả về 0. Vì vậy, nếu số giống như [1,2 , 3,4,5,6,7,8], thì đầu ra sẽ là 5. Dãy con dài nhất là Fibonacci giống như [1,2,3,5,8].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ret:=0
-
tạo một ánh xạ m, n:=kích thước của mảng A
-
tạo một ma trận gọi là dp có kích thước n x n
-
cho tôi trong phạm vi từ 0 đến n - 1
-
m [A [i]]:=i
-
đối với j trong phạm vi i - 1, giảm xuống 0
-
yêu cầu:=A [i] - A [j]
-
khi A [i] - A [j]
-
dp [i, j]:=max of dp [i, j], dp [j, m [A [i] - A [j]]] + 1
-
-
nếu không thì dp [i, j]:=max của dp [i, j] và 2
-
ret:=max của ret và dp [i, j]
-
-
-
trả về ret khi ret> =3 nếu không thì trả về 0.
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[1,2,3,4,5,6,7,8]
Đầu ra
5