最长的斐波那契子序列的长度-873

[sl1673495]

如果序列  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%）

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

dp[i] 表示从 0 ~ i 可以得到的斐波那契子序列（或者长度小于 3，作为一个预备可选项）的所有组合。数组里的每一项需要分别维护：

• sum: 当前斐波那契子序列的最后两项的和。
• head：当前斐波那契子序列的最后两项的第一个数字。
• len: 当前斐波那契子序列长度。

之所以只需要关心 最后两项，是因为能否和下一个数字组成斐波那契子序列，只需要考虑上一个子序列的尾部两个数字即可，比如 [1, 2, 3] 是一个斐波那契子序列，但是它之后去和 5 组合，只需要考虑 [2, 3] 与 5 的可组合性。当我们记录下来 sum 为 5了以后，只需要去找到 5 这个数字，就确定可以组合成一个斐波那契子序列了。

而记录 head 是因为，找到了 [2, 3, 5] 以后，是需要把 2 这一项给删除掉，以 3 + 5 作为下一个目标 sum的，所以必须要有地方记录下来 2 这个数字。

而下一项的 head 应该是 3，这个如何得出呢？其实只需要用上一次记录的 sum: 5 减去上一次的 head: 2，即可得出上一次的末尾 3，作为下一次的 head。

也就是说 sum 其实是两个元素所组成的数组在不断的向后“滑动”，上一次的尾部就是下一次的头部。

最后，在求出的所有结果里找出 len 最大的那一项就可以了。

/**
 * @param {number[]} A
 * @return {number}
 */
let lenLongestFibSubseq = function (A) {
  let n = A.length
  if (!n) return 0

  let dp = []
  dp[0] = [{ sum: A[0], len: 1, head: A[0] }]

  for (let i = 1; i < n; i++) {
    let cur = A[i]
    let selections = [{ sum: cur, len: 1, head: cur }]
    for (let j = 0; j < i; j++) {
      for (let selection of dp[j]) {
        const { sum, len, head } = selection
        // 长度为1 和任何值都可以组成一个选项
        if (len === 1) {
          selections.push({ sum: sum + cur, len: 2, head: sum })
        } else if (sum === cur) {
          // 长度大于1的时候 只有之前的和与当前数字相等 才可以组成一个斐波那契序列
          // 在组成新的组合的时候 要去掉之前的头部 比如[1, 2]和3组合 变成 [2, 3]
          // 并且下一步需要求的目标和也需要是2+3=5 所以sum需要在之前的基础上减去头部1，再加上尾部3
          // 下一步的head 其实就是这一步的末尾数字 直接用sum-head就可以得出 比如3-1=2
          selections.push({
            sum: sum - head + cur,
            len: len + 1,
            head: cur - head,
          })
        }
      }
    }
    dp[i] = selections
  }

  let res = Math.max(...dp.flat().map(({ len }) => len))
  return res >= 3 ? res : 0
}

[zhimazz]

Runtime: 9024 ms, faster than 5.39% of JavaScript online submissions for Length of Longest Fibonacci Subsequence. Memory Usage: 100.3 MB, less than 7.78% of JavaScript online submissions for Length of Longest Fibonacci Subsequence. 还有没有更优的方法

[eynait1010]

function lenLongestFibSubseq(arr: number[]): number {
    const numMap = arr.reduce((acc, cur, idx) => {
        return acc.set(cur, idx)
    }, new Map());
    let result = 0
    const dpTable = new Array(arr.length).fill('').map(_ => new Array(arr.length - 1).fill(0))
    for (let i = 2; i < arr.length; i++) {
        for (let j = 1; j < i; j++) {
            const lastValue = arr[i] - arr[j]
            if (lastValue >= arr[j]) {
                continue
            }
            if (numMap.has(lastValue)) {
                dpTable[i][j] = Math.max(3, dpTable[j][numMap.get(lastValue)] + 1)
                result = Math.max(result, dpTable[i][j])
            }
        }
    }
    return result
};