Dãy X gọi là Fibonacci-like nếu n≥3 và X[i]+X[i+1]=X[i+2]. Cho mảng A tăng nghiêm ngặt, tìm độ dài dãy con Fibonacci-like dài nhất. Nếu không có trả về 0.
Ví dụ: [1,2,3,4,5,6,7,8] → 5 ([1,2,3,5,8]).
Giải pháp DP:
m[value] = index
dp[i][j] = độ dài dãy Fibonacci kết thúc bằng A[j], A[i] (j
Duyệt i, j
Cập nhật ret = max(ret, dp[i][j])
Trả về ret≥3 ? ret : 0
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int lenLongestFibSubseq(vector<int> & A) { int ret = 0, n = A.size(); unordered_map<int,int> m; 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(req<A[j] && m.count(req)) dp[i][j]=max(dp[i][j], dp[j][m[req]]+1); else dp[i][j]=max(dp[i][j],2); ret=max(ret,dp[i][j]); } } return ret>=3?ret:0; } }; int 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