Skip to main content

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

Tips

题目类型: Dynamic Programming

题目​

如果序列 X_1, X_2, ..., X_n 满足下列条件, 就说它是斐波那契式:

  • n >= 3
  • 对于所有 i + 2 <= n, 都有 X_i + X_{i + 1} = X_{i + 2}

给定一个严格递增的正整数数组形成序列 arr, 找到 arr 中最长的斐波那契式的子序列的长度. 如果一个不存在, 返回 0.

提示:
  • 3 <= arr.length <= 1000
  • 1 <= arr[i] < arr[i + 1] <= 10⁹
示例
输入: arr = [1, 2, 3, 4, 5, 6, 7, 8]
输出: 5
解释: 最长的斐波那契式子序列为[(1, 2, 3, 5, 8)]
输入: arr = [1, 3, 7, 11, 12, 14, 18]
输出: 3
解释: 最长的斐波那契式子序列有 [1, 11, 12], [3, 11, 14] 以及 [7, 11, 18]

题解​

如果是斐波那契数列, 那么存在三个下标 i, j, k, 使得 arr[i] > arr[j] > arr[k], 且 arr[k] + arr[j] === arr[i]. 因为题目提供的 arr 是严格递增的, 那么 arr[i] > arr[j] > arr[k] 就等价于 i > j > k.

当下标 i 确定了, 任何小于下标 i 的下标 j 都可能满足 arr[j] 是某个斐波那契式子序列中 arr[i] 前面的一个数字, 因此说要确定斐波那契的后两个数字, 才能确定整个斐波那契式子序列.

因此初始化一个二维数组 dp, 使得表示以每个下标对的元素作为最后两个数字的斐波那契式子序列的最大长度, 即当 i > j 时, dp[j][i] 表示以 arr[j] 和 arr[i] 作为最后两个数字的斐波那契式子序列的最大长度.

当确定了后两个数字下标 j, i, 需要找到第一个数字下标 k, 使得 k < j, 且 arr[k] + arr[j] === arr[i]. 这样就可以通过 dp[k][j] 递推出 dp[j][i], 具体状态转移方程如下:

  • dp[j][i] = Math.max(dp[k][j] + 1, 3) // 0 <= k < j, 最短的斐波那契数列是 3, 所以跟 3 比较
  • dp[j][i] = 0 // 不存在 k, 或者 k >= j
/**
 * @param {number[]} arr
 * @return {number}
 */
var lenLongestFibSubseq = function (arr) {
  const n = arr.length

  const map = new Map()
  for (let i = 0; i < n; i++) {
    map.set(arr[i], i)
  }

  const dp = new Array(n).fill(0).map(() => new Array(n).fill(0))

  let ans = 0
  for (let i = 0; i < n; i++) {
    for (let j = n - 1; j >= 0; j--) {
      // 一种优化手段, 如果前一个数字都不及后一个数字的一半, 是不可能构成斐波那契数列的
      if (arr[j] * 2 <= arr[i]) {
        break
      }

      if (map.has(arr[i] - arr[j])) {
        const k = map.get(arr[i] - arr[j])
        dp[j][i] = Math.max(dp[k][j] + 1, 3)
        ans = Math.max(ans, dp[j][i])
      }
    }
  }

  return ans
}