问题
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
示例
输入： arr = [1,2,3,4,5,6,7,8]
输出： 5
解释： 最长的斐波那契式子序列为 [1,2,3,5,8] 。
解答
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size(), res = 0;
unordered_map<int, int> ump;
for (int i = 0; i < n; i++)
ump[arr[i]] = i;
int dp[n][n]; bzero(dp, sizeof dp); // dp[i][j]指以i、j结尾的最长fib序列长度
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int arr_k = arr[j] - arr[i]; // dp[i][j]由dp[k][i] + 1求得
if (arr_k < arr[i] && ump.count(arr_k)) { // 由递增性质，保证k在i前面且存在这样的k
int k = ump[arr_k];
dp[i][j] = max(dp[i][j], dp[k][i] + 1);
res = max(res, 2 + dp[i][j]);
}
}
}
return res;
}
};
重点思路
对于求解“满足某一条件”的最长子序列，我们可以联想到【LeetCode-300】最长递增子序列的动态规划做法。fib序列可以由相邻的两个数唯一确定，对于“最长递增子序列”那道题，我们使用dp[i]表示以i结尾的最长递增子序列，这道题中，我们使用dp[i][j]表示以i, j结尾的最长fib序列。