1、思路

• 用一个二维数组来做DP，它的行表示以arr[i]结尾的斐波那契数列最大长度，列表示以arr[j]作为倒数第二个元素的斐波那契数列最大长度。i的取值范围为[1, n - 1]，j的取值范围为[0, n - 2]；

• 若存在arr[k]使得arr[i] = arr[j] + arr[k]，其中0 <= k < j < i < n，则f(i, j) = f(j, k) + 1，这就是状态转移方程；

• 采用二重循环，时间复杂度为 $O(N^2)$ ，采用二维数组，空间复杂度也是 $O(N^2)$ 。

2、代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        unordered_map<int, int> hash;
        for (int i = 0; i < arr.size(); ++ i)
        {
            hash[arr[i]] = i;   //哈希表建为数组元素的值，值为元素下标
        }

        vector<vector<int>> dp(arr.size(), vector<int>(arr.size()));
        int res = 2;            //斐波那契数列合法长度最短为3，这里初始化为2，便于dp时做累加

        for (int i = 1; i < arr.size(); ++ i)
        {
            for (int j = 0; j < i; ++ j)
            {
                //若存在 arr[k] 使得 arr[i] = arr[j] + arr[k] ，则取得这个元素的下标
                int k = (hash.find(arr[i] - arr[j]) != hash.end()) ? hash[arr[i] - arr[j]] : -1;
                dp[i][j] = k >= 0 && k < j ? dp[j][k] + 1 : 2;  //状态转移方程

                res = max(res, dp[i][j]);
            }
        }

        return res > 2 ? res : 0;   //若结果为2，说明数组中不存在斐波那契数列
    }
};