[LeetCode]Length of Longest Fibonacci Subsequence

斐波那契数列由前两项决定，所以我们遍历前两项的所有可能，然后去题目给的数字里验证最长的数列是多少。前两项总共的组合有O(N ^ 2)个，对于斐波那契数列，f(n) > 2 * f(n - 2)是必定成立的，数列每隔两项就至少会翻一倍。所以最长的序列也就2 * log M，M为数组的最大值。时间复杂度O(N^2 * log M)，空间复杂度O(n)，用hash set存，代码如下：



既然数列可以由前两项决定，那当然也可以由后两项决定，那么我们就可以参考LIS的的思路。DP[i][j]代表以A[i], A[j]两项结尾的数列，对于每个j，我们遍历之前的所有i，如果输入数组中存在k = A[i] - A[j] && k < A[j]，我们更新dp[A[i]][A[j]] = max(dp[A[i]][A[j]], dp[k][A[i]] + 1)。时间复杂度O(n ^ 2)，空间复杂度O(n^2)，代码如下：