548，动态规划解最长的斐波那契子序列的长度
This is the last game so make it count, it’s now or never.
不要辜负这最后的比赛，时不我待。
问题描述
如果序列X_1,X_2,...,X_n满足下列条件，就说它是斐波那契式的：
n>=3
对于所有i+2<=n，都有X_i+X_{i+1}=X_{i+2}
给定一个严格递增的正整数数组形成序列，找到A中最长的斐波那契式的子序列的长度。如果一个不存在，返回0。
（回想一下，子序列是从原序列A中派生出来的，它从A中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如，[3,5,8]是[3,4,5,6,7,8]的一个子序列）
示例 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
（对于以Java，C，C++，以及C#的提交，时间限制被减少了50%）
暴力解决
斐波那契数列满足的条件是前两项的和等于第3项的值。暴力求解的方式就是先固定第1项和第2项的值，然后来查找第3项，如果数组中存在第3项的值，说明这3项可以构成一个斐波那契数列，然后在更新第1项和第2项的值，更新结果是
(first, second) -> (second, first+second)
接着重复上面的判断……记录最长的即可。
因为题中说了是一个递增的正整数数组，所以我们可以先把数组中的元素全部存放到集合Set中，查找第3项的时候直接从集合Set中查找即可，来看下代码。
1public int lenLongestFibSubseq(int[] A) {
2 int size = A.length;
3 //先把数组A中的所有元素都存储在Set中
4 Set<Integer> set = new HashSet<>();
5 for (int num : A)
6 set.add(num);
7 //记录构成的最长斐波那契数列的长度
8 int maxLength = 0;
9 for (int i = 0; i < size; ++i)
10 for (int j = i + 1; j < size; ++j) {
11 //斐波那契数列的第一项
12 int first = A[i];
13 //斐波那契数列的第二项
14 int second = A[j];
15 //当前斐波那契数列的长度
16 int len = 2;
17 //斐波那契数列前两项和等于第三项的值，这里
18 //判断数组A中是否存在前两项的和
19 while (set.contains(first + second)) {
20 //如果能构成斐波那契数列，我们需要更新后面的值，
21 //(first, second) -> (second, first+second)
22 second = first + second;
23 first = second - first;
24 //记录当前能构成的斐波那契数列的长度
25 len++;
26 }
27 //更新最大的斐波那契数列长度
28 if (len > maxLength)
29 maxLength = len;
30 }
31 //能构成斐波那契数列，长度必须大于等于3，如果小于3，
32 //说明不能构成斐波那契数列，直接返回0，否则返回maxLength
33 return maxLength >= 3 ? maxLength : 0;
34}
动态规划解决
动态规划首先要找出状态的定义和状态转移公式。定义dp[i][j]表示以A[i]和A[j]结尾的斐波那契数列的最大长度。也就是[……，A[i]，A[j]]构成的斐波那契数列的最大长度。
状态转移公式就是，如果以A[i]和A[j]结尾能构成斐波那契数列，那么在这个数列A[i]之前必定有一个值A[k]满足A[k]+A[i]=A[j]；所以如果确定了A[i]和A[j]的值之后，我们可以往前来找A[k]，那么转移公式就是
dp[i][j]=dp[k][i]+1;
所以大致代码我们就很容易写出来了。
1 for (int j = 2; j < length; j++) {//确定A[j]
2 for (int i = j - 1; i > 0; i--) {//确定A[i]
3 for (int k = i - 1; k >= 0; k--) {//往前查找A[k]
4 if (A[k] + A[i] == A[j]) {
5 dp[i][j] = dp[k][i] + 1;
6 //如果找到就终止内层循环，不在往前查找了
7 break;
8 } else if (A[k] + A[i] < A[j]) {
9 //题中说了是递增的正整数数组，如果当前A[k]
10 //小了，那么前面的就更小，没有合适的，没必要
11 //在往前找了，直接终止内层循环
12 break;
13 }
14 }
15 maxLength = Math.max(maxLength, dp[i][j]);
16 }
17 }
我们来看下最终代码
1public int lenLongestFibSubseq(int[] A) {
2 //记录最大的斐波那契数列的长度
3 int maxLength = 0;
4 int length = A.length;
5 int[][] dp = new int[length][length];
6 for (int j = 2; j < length; j++) {//确定A[j]
7 for (int i = j - 1; i > 0; i--) {//确定A[i]
8 for (int k = i - 1; k >= 0; k--) {//往前查找A[k]
9 if (A[k] + A[i] == A[j]) {
10 dp[i][j] = dp[k][i] + 1;
11 //如果找到就终止内层循环，不在往前查找了
12 break;
13 } else if (A[k] + A[i] < A[j]) {
14 //题中说了是递增的正整数数组，如果当前A[k]
15 //小了，那么前面的就更小，没有合适的，没必要
16 //在往前找了，直接终止内层循环
17 break;
18 }
19 }
20 maxLength = Math.max(maxLength, dp[i][j]);
21 }
22 }
23 //注意数列长度统计的时候没有统计前面两项，如果能构成
24 //斐波那契数列最后还需要加上
25 return maxLength > 0 ? maxLength + 2 : 0;
26}
动态规划代码优化
上面代码确定A[j]和A[i]，查找A[k]的时候是一个个往前查，整个计算时间复杂度比较高，我们还可以把遍历过的A[j]和他对应的下标存放到map中，在查找的时候直接从map中查找，这样时间复杂度就会从O(n^3)降到O(n^2)，来看下代码。
1public int lenLongestFibSubseq(int[] A) {
2 //记录最大的斐波那契数列的长度
3 int maxLength = 0;
4 int length = A.length;
5 int[][] dp = new int[length][length];
6 Map<Integer, Integer> map = new HashMap<>();
7 for (int j = 0; j < length; j++) {//确定A[j]
8 map.put(A[j], j);
9 for (int i = j - 1; i > 0; i--) {//确定A[i]
10 //因为是递增的，如果A[j]和A[i]之间相差比较大，
11 //就不需要再往前查找了
12 if (A[j] - A[i] >= A[i])
13 continue;
14 //通过map往前查找A[k]
15 int k = map.getOrDefault(A[j] - A[i], -1);
16 //如果k不等于-1，说明在数组中找到了A[k]这个值
17 if (k >= 0) {
18 dp[i][j] = dp[k][i] + 1;
19 maxLength = Math.max(maxLength, dp[i][j]);
20 }
21 }
22 }
23 return maxLength > 0 ? maxLength + 2 : 0;
24}
动态规划+双指针代码优化
对于题中的条件是递增的数量，也就是有序的，所以我们还可以使用双指针来解决，当确定A[j]之后，我们在A[j]的前面来使用两个指针来找和等于A[j]的两个值，这里以示例一为例看下视频
最后再来看下代码
1public int lenLongestFibSubseq(int[] A) {
2 //记录最大的斐波那契数列的长度
3 int maxLength = 0;
4 int length = A.length;
5 int[][] dp = new int[length][length];
6 for (int j = 2; j < length; j++) {//确定A[j]
7 //左右两个指针
8 int left = 0;
9 int right = j - 1;
10 while (left < right) {
11 //两个指针指向值的和
12 int sum = A[left] + A[right];
13 if (sum > A[j]) {
14 //因为数组是递增的，如果两个指针指向的值
15 //大了，那么右指针往左移一步来减小他俩的和
16 right--;
17 } else if (sum < A[j]) {
18 //如果两个指针指向的值小了，那么左指针往
19 //右移一步来增大他俩的和
20 left++;
21 } else {
22 //如果两个指针指向的和等于A[j]，说明这两个指针
23 //指向的值和A[j]可以构成斐波那契数列
24 dp[right][j] = dp[left][right] + 1;
25 maxLength = Math.max(maxLength, dp[right][j]);
26 right--;
27 left++;
28 }
29 }
30 }
31 return maxLength > 0 ? maxLength + 2 : 0;
32}
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。