题目描述

定义序列$ X_1, X_2, …, X_n$ 是斐波那契额数列当且仅当:

1. n >= 3
2. $X_i + X_{i+1} = X_{i+2}$对于所有的$ i + 2 <= n$

给定严格递增的正整数数列A，找到A中最长的斐波那契子序列的长度。

样例

输入：[1,2,3,4,5,6,7,8]
输出：5
说明：最长的斐波那契额子序列为[1,2,3,5,8]

算法

(动态规划) $O(n^2)$

动态规划，斐波那契数列只要最后两个数字确定了，那么整条序列就确定了，因此我们可以通过判断 $nums[j]$ 和 $nums[i] (j<i)$ 能否接到已有的斐波那契数列上，如果满足存在$k<j<i$，有 $nums[k]+nums[j]=nums[i]$，那么就可以接在以 $nums[k]$ 和 $nums[j]$ 结尾的斐波那契子序列上，依次类推。

用数组 $dp[j][i] (j<i)$ 记录表示以 $nums[j]$ 和 $nums[i]$ 为最后两个数的斐波那契子序列的长度。递推公式为: 如果满足 $nums[prev]+nums[j]=nums[i]$，则 $dp[j][i]=dp[prev][j]+1$。由于任意两个数字都可以构成斐波那契数列的开头，因此初始化dp数组中每个位置的值均为2。

另外可以用哈希表(unordered_map)的方式迅速找到是否存在prev使得 $nums[prev]+nums[j]=nums[i]$。

时间复杂度分析：需要遍历二维数组，复杂度为$O(n^2)$。

C++ 代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& nums) {
        unordered_map<int,int>mp;//以nums中的每个值为key，对应的下标为value
        int maxlen = 0;//maxlen是返回结果
        for(int i = 0;i<nums.size();i++){
            mp.insert(make_pair(nums[i],i));
        }
        vector<vector<int>>dp;
        for(int i = 0;i<nums.size();i++){//初始化dp数组
            vector<int>vec;
            for(int j = 0;j<nums.size();j++)
                vec.push_back(2);
            dp.push_back(vec);
        }
        for(int i = 1;i<nums.size();i++){
            for(int j =i-1;j>=0;j--){
                int preval=nums[i]-nums[j];
                if(preval>=nums[j])//要求preval的下标必须小于j
                    break;
                unordered_map<int,int>::iterator it = mp.find(preval);
                if(it!=mp.end()){
                    dp[j][i]=max(dp[j][i],dp[it->second][j]+1);//it->second就是preval的下标
                    if(dp[j][i]>maxlen)
                        maxlen=dp[j][i];//更新maxlen
                }

            }
        }
        return maxlen;
    }
};