跳转至

LeetCode: 873. 最长的斐波那契子序列的长度

1、题目描述

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

2、解题思路

​ 直接看到这道题,首先能想到下面的解法

  • 从第一个元素开始,第一个元素与第二个元素之和,是否存在,如果存在,顺着当前序列判断下去
  • 然后第一个元素与第三个元素之和,是否存在,如果存在,继续判断下去
  • 经过这样的判断,确实能够得到答案,但是时间复杂度是O(n^3),所以不太符合要求

​ 这样的题目,可以考虑使用动态规划,利用前面已经计算的结果来做

  • 建立一个字典,默认值是0,键则用两个数字组成的元组
  • 当我们判断两个数字的时候,看看是不是形成了斐波那契序列,如果是,就保存到字典中,键为起那两个数字所形成的斐波那契数列值加1
class Solution:
    def lenLongestFibSubseq(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        buff = collections.defaultdict(int)
        s = set(A)

        ans = 0

        for i in range(2, len(A)):
            for j in range(i):
                if A[i] - A[j] < A[j] and A[i] - A[j] in s:
                    buff[(A[i], A[j])] = buff.get((A[j], A[i] - A[j]), 2) + 1
                    ans = max(ans, buff[(A[i], A[j])])

        return ans