Problem: 873. Length of Longest Fibonacci Subsequence 最长的斐波那契子序列的长度
解题过程
对每两个数字a, c，若差s存在且在两者前面s, …, a, c；那么就可以递归查找下去，将s赋值给a，将a赋值给c，并求得最大长度
Code
class Solution { public: unordered_map<int, int> ump; int lenLongestFibSubseq(vector<int>& arr) { for(int i = 0; i < arr.size(); i++) { ump[arr[i]] = i; } int n = arr.size(), mid = 1, tail = 2, su, num, mx = INT_MIN; for(int i = 2; i < n; i++) { for(int j = i - 1; j > 0; j--) { tail = i; mid = j; num = 2; while(true) { su = arr[tail] - arr[mid]; if(ump.find(su)!=ump.end() && ump[su] < mid) { num++; tail = mid; mid = ump[su]; } else { break; } if(mid == 0) break; } mx = max(mx, num); } } if(mx==2) return 0; return mx; } };官方题解的动态规划方式
class Solution { public: unordered_map<int, int> ump; int lenLongestFibSubseq(vector<int>& arr) { for(int i = 0; i < arr.size(); i++) { ump[arr[i]] = i; } int n = arr.size(), mx = INT_MIN, su; vector<vector<int>> dp(n, vector<int>(n)); for(int i = 2; i < n; i++) { for(int j = i - 1; j > 0; j--) { su = arr[i] - arr[j]; if(ump.find(su)!= ump.end() && ump[su] < j) { dp[j][i] = max(dp[ump[su]][j] + 1, 3); } mx = max(mx, dp[j][i]); } } if(mx==2) return 0; return mx; } };
