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

难度: Medium

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

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

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

（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

提示：

3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 10^9

注意：本题与主站 873 题相同： https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/

Submission

运行时间: 468 ms

内存: 23.6 MB

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        maps = {arr[i]: i for i in range(n)}
        dp = [[0]*n for _ in range(n)]
        res = 0
        for i in range(2,n):
            for j in range(i-1,0,-1):
                if arr[j]*2 <= arr[i]:
                    break
                if arr[i]-arr[j] in maps:
                    k = maps[arr[i]-arr[j]]
                    dp[i][j] = max(dp[j][k]+1,3)
                    res = max(res, dp[i][j])
        return res

Explain

该题解采用了动态规划的方法。首先，利用哈希表maps存储数组中每个元素的索引，以便快速查找。dp[i][j]表示以arr[i]和arr[j]为最后两个元素的斐波那契子序列的最大长度。通过双层循环遍历所有可能的arr[i]和arr[j]组合，对每个组合，计算差值arr[i]-arr[j]，并检查该差值是否存在于数组中。如果存在，说明可以形成一个斐波那契子序列，dp表更新为dp[j][k]+1，k是差值对应的索引。循环中还使用一个变量res来维护全局的最长子序列长度。注意，为了避免无效计算，当arr[j]的两倍小于等于arr[i]时，内层循环会提前终止。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

# Definition for the solution class

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr) # 获取数组长度
        maps = {arr[i]: i for i in range(n)} # 创建哈希表存储数组元素及其索引
        dp = [[0]*n for _ in range(n)] # 初始化动态规划表
        res = 0 # 初始化最长斐波那契子序列的长度
        for i in range(2, n): # 从第三个元素开始
            for j in range(i-1, 0, -1): # 从i的前一个元素开始向前遍历
                if arr[j]*2 <= arr[i]: # 如果当前元素的两倍小于等于arr[i]，停止当前循环
                    break
                if arr[i]-arr[j] in maps: # 如果差值在数组中，可以形成斐波那契子序列
                    k = maps[arr[i]-arr[j]] # 获取差值对应的索引
                    dp[i][j] = max(dp[j][k]+1, 3) # 更新dp表，至少为3（因为斐波那契序列至少需要三个数）
                    res = max(res, dp[i][j]) # 更新最长长度
        return res # 返回结果

Explore

在动态规划中，dp数组的初始化值通常代表一个基础状态，对于斐波那契序列问题，0表示没有有效的斐波那契序列的初始状态。在更新dp[i][j]时，如果直接赋值为dp[j][k]+1，在没有确认存在一个有效的斐波那契子序列（即至少包含三个数）之前，这种更新可能会导致错误的结果。这是因为dp[j][k]+1可能仅仅是基于一个非斐波那契序列的两个数的错误延伸。因此，我们需要验证当前序列至少能形成一个包含三个数字的斐波那契序列。

斐波那契序列定义中，至少包含三个元素，这些元素满足后一个数是前两个数的和。因此，在动态规划更新中，即使通过dp[j][k]+1找到了一个潜在的序列增长方式，我们还需要确保这个更新的序列长度至少为3，这是斐波那契序列的基本要求。如果不这样做，我们可能会错误地将长度小于3的序列计算在内，这不符合斐波那契序列的定义。

这一优化的逻辑基于斐波那契数列的性质：在任何斐波那契序列中，任意两个连续的数a和b（a < b），下一个数c（c = a + b）总是大于b。因此，如果在数组中存在某个元素arr[i]，使得arr[j]*2 <= arr[i]，则不存在任何数k使得arr[k] + arr[j] = arr[i]（因为arr[j] < arr[k]应该成立，但arr[k]至少应该为arr[i] - arr[j]，此时arr[j] < arr[i] - arr[j]不成立）。所以，当arr[j]的两倍小于等于arr[i]时，意味着不可能通过当前的j和任何更小的数形成斐波那契序列，提前终止循环可以减少不必要的计算。