最长的斐波那契子序列的长度（二）

解决方案

动态规划
思路和算法

如果数组 arr 中存在三个下标 i、j、k 满足 arr[i]>arr[j]>arr[k] 且 arr[k]+arr[j]=arr[i] ，则 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] 作为最后两个数字的斐波那契子序列的最大长度。

初始时 dp 中的所有值都是 0 。为了计算 dp[j][i] 的值，需要得到该斐波那契序列中位于 arr[j] 前面的数字，该数字是 arr[i]−arr[j] 。如果 arr[i]−arr[j] 存在于数组 arr 中，且该数字小于 arr[j] ，则用 k 表示其下标，有 arr[k]+arr[j]=arr[i] 。

因此在以 arr[k] 和 arr[j] 作为最后两个数字的斐波那契子序列的后面添加 arr[i] ，即可得到以 arr[j] 和 arr[i] 作为最后两个数字的斐波那契子序列。根据斐波那契子序列的定义可知，斐波那契子序列的长度至少为 3 。

当 dp[k][j]≥3 时，dp[j][i]=dp[k][j]+1 。当 dp[k][j]<3 时，以 arr[k] 和 arr[j] 作为最后两个数字的斐波那契子序列并不存在，但是以 arr[j] 和 arr[i] 作为最后两个数字的斐波那契子序列存在，此时有 dp[j][i]=3 。假设当 arr[i]−arr[j] 不存在于数组中时，k<0 ，则完整的状态转移方程如下：

实现方面可以利用数组 arr 的单调性优化。由于数组 arr 是严格单调递增的，因此在确定下标 i 的情况下可以反向遍历下标 j ，计算 dp[j][i] 的值，只有当 arr[j]×2>arr[i] 时才满足 arr[k]<arr[j] ，当 arr[j]×2≤arr[i] 时不需要对当前下标 i 继续遍历更小的下标 j 。

代码

Python3

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