1.题目解析

题目来源： LCR 093.最长的斐波那契子序列——力扣

测试用例 

2.算法原理

1.状态表示

由题目可知斐波那契数列至少需要三个数，所以以往的一维dp表显然无法完成状态的表示，所以需要二维的dp表来表示，这里首先表示斐波那契数列子序列的后两位数字

dp[i][j]:以第i个位置与第j个位置为结尾的斐波那契子序列的最长长度(i<j)

2.状态转移方程

由前面的状态表示我们知道需要找到斐波那契子序列就要找到最后两个数的前一个数才能构成长度至少为3的子序列，为了不逐个遍历我们不妨将数组元素与其下标绑定存在哈希表中，其中数组元素为key元素，数组元素下标为value元素，即使用key查找value元素，这时需要满足第三个数存在且在最后两个数的前面表达式为：

dp[i][j] = dp[hash[a]][i] + 1;条件是hash.count(a) && a < arr[i]

3.初始化

一直dp表存储的是斐波那契子序列的最后两个数，所以哪怕没有一条斐波那契子序列最小长度也为2，那么不妨将dp表的所有元素均初始化为2

4.填表顺序

dp表是一个二维表，每次填表都需要找到dp[hash[a]][i]，已知hash[a] < i < j，所以一定是从上至下填表，左右顺序随意即可

5.返回值

返回dp表中的最大值即可，注意如果没有找到一条斐波那契子序列那么ret就为2，最后需要返回0，这里需要特殊判断

3.实战代码

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {int n = arr.size();unordered_map<int,int> hash;// 哈希表对应位置存储的是对应的下标for(int i = 0;i < n;i++){hash[arr[i]] = i;}int ret = 2;vector<vector<int>> dp(n,vector<int>(n,2));for(int j = 2;j < n;j++){for(int i = 1;i < j;i++){int a = arr[j] - arr[i];if(a < arr[i] && hash.count(a)){dp[i][j] = dp[hash[a]][i] + 1;}ret = max(ret,dp[i][j]);}}return ret < 3 ? 0 : ret;}
};