LeetCode 873. 最长的斐波那契子序列的长度（动态规划）

示例 1：
输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。

示例 2：
输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。
 
提示：
3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
    	unordered_set<int> s;
    	for(int Ai : A)
    		s.insert(Ai);
    	int a, b, c, len = 0, maxlen = 0;
    	for(int i = 0, j; i < A.size(); ++i)
    	{
    		for(j = i+1; j < A.size(); ++j)
    		{
                len = 2;
    			c = A[i]+A[j];
                a = A[i];
                b = A[j];
				while(s.count(c))
				{
					len++;
					maxlen = max(maxlen, len);
					a = b;
					b = c;
					c = a+b;
				}
    		}
    	}
    	return maxlen;
    }
};

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
    	unordered_map<int,int> m;//val, idx
        int i, j, prevAi, idx, maxlen = 0, n = A.size();
    	for(i = 0; i < n; ++i)
    		m[A[i]] = i;
    	vector<vector<int>> dp(n,vector<int>(n,0));
    	//dp[i][j] 表示以 A[i],A[j]结尾的序列长度
    	for(i = 0; i < n; ++i)
    		for(j = i+1; j < n; ++j)
    			dp[i][j] = 2;
    	for(i = 0; i < A.size(); ++i)
    	{
    		for(j = i+1; j < A.size(); ++j)
    		{
    			prevAi = A[j]-A[i];//A[i] 前一位数
                if(m.count(prevAi))
                {
                	idx = m[prevAi];//前一位数下标
                	if(idx < i)//在 i 前面
                	{
                        dp[i][j] = max(dp[i][j],dp[idx][i]+1);//更长的序列
                        maxlen = max(maxlen,dp[i][j]);
                    }
                }
    		}
    	}
    	return maxlen;
    }
};