题目：最长的斐波那契子序列的长度

  • 如果序列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. 输入: [1,2,3,4,5,6,7,8]
  2. 输出: 5
  3. 解释:
  4. 最长的斐波那契式子序列为：[1,2,3,5,8] 。
示例2：
  1. 输入: [1,3,7,11,12,14,18]
  2. 输出: 3
  3. 解释:
  4. 最长的斐波那契式子序列有：
  5. [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%）

来源：力扣（LeetCode）第873题

链接：https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence

分析：

外来题解：

方法一：使用 Set 的暴力法

思路

  • 每个斐波那契式的子序列都依靠两个相邻项来确定下一个预期项。例如，对于2, 5我们所期望的子序列必定以7, 12, 19, 31等继续。
  • 我们可以使用 Set 结构来快速确定下一项是否在数组 A 中。由于这些项的值以指数形式增长，最大值10^9≤10^9 的斐波那契式的子序列最多有 43 项。

算法

  • 对于每个起始对A[i], A[j]，我们保持下一个预期值y = A[i] + A[j]和此前看到的最大值 x = A[j]。如果 y 在数组中，我们可以更新这些值(x, y) -> (y, x+y)。
  • 此外，由于子序列的长度大于等于 3 只能是斐波那契式的，所以我们必须在最后进行检查 ans >= 3 ? ans : 0。

方法二：动态规划

思路

  • 将斐波那契式的子序列中的两个连续项 A[i], A[j] 视为单个结点 (i, j)，整个子序列是这些连续结点之间的路径。
  • 例如，对于斐波那契式的子序列(A[1] = 2, A[2] = 3, A[4] = 5, A[7] = 8, A[10] = 13)，结点之间的路径为 (1, 2) <-> (2, 4) <-> (4, 7) <-> (7, 10)。
  • 这样做的动机是，只有当A[i] + A[j] == A[k] 时，两结点 (i, j) 和 (j, k) 才是连通的，我们需要这些信息才能知道这一连通。现在我们得到一个类似于 最长上升子序列 的问题。

算法

  • 设 longest[i, j] 是结束在 [i, j] 的最长路径。那么 如果 (i, j) 和 (j, k) 是连通的， longest[j, k] = longest[i, j] + 1。
  • 由于 i 由 A.index(A[k] - A[j]) 唯一确定，所以这是有效的：我们在 i 潜在时检查每组 j < k，并相应地更新 longest[j, k]。

代码：

  • 暴力查询法：

    1. class Solution {
    2. public int lenLongestFibSubseq(int[] A) {
    3.     int len = A.length;int ans = 0;
    4.     Set<Integer> hs = new HashSet();
    5.     for (int i = 0; i < len; i++) hs.add(A[i]);
    6.     for (int i = 0; i < len; i++) {
    7.         for (int j = i + 1; j < len; j++) {
    8.             int x = A[j], y = A[i] + A[j];
    9.             int cout = 2;
    10.             while (hs.contains(y)) {
    11.                 cout++;
    12.                 int tmp = x;
    13.                 x = y;
    14.                 y += tmp;
    15.             }
    16.             ans = Math.max(ans, cout);
    17.         }
    18.     }
    19.     return ans > 2 ? ans : 0;
    20. }
    21. }

  • dp

    1. class Solution {
    2. public int lenLongestFibSubseq(int[] A) {
    3.     int len = A.length;int ans = 0;
    4.     Map<Integer, Integer> index = new HashMap();
    5.     for (int i = 0; i < len; i++) index.put(A[i], i);
    6.     Map<Integer, Integer> dp = new HashMap();
    7.     for (int k = 0; k < len; k++) {
    8.         for (int j = 0; j < k; j++) {
    9.             int i = index.getOrDefault(A[k] - A[j], -1);
    10.             if (i >= 0 && i < j) {
    11.                 // 这个地方要注意，i乘以len再加上j是为了区分i和j的顺序，因为i+j和j+i是一样的
    12.                 int cout = dp.getOrDefault(i * len + j, 2) + 1;
    13.                 dp.put(j * len + k, cout);
    14.                 ans = Math.max(ans, cout);
    15.             }
    16.         }
    17.     }
    18.     return ans > 2 ? ans : 0;
    19. }
    20. }