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

解决方案动态规划思路和算法如果数组 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] 等价于 ijk 。当下标 i 确定时任何小于下标 i 的下标 j 都可能满足 arr[j] 是某个斐波那契子序列中 arr[i] 前面的一个数字因此只有当确定斐波那契子序列的最后两个数字时才能确定整个斐波那契子序列。定义二维数组 dp 表示以每个下标对的元素作为最后两个数字的斐波那契子序列的最大长度。当 ij 时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] 不存在于数组中时k0 则完整的状态转移方程如下实现方面可以利用数组 arr 的单调性优化。由于数组 arr 是严格单调递增的因此在确定下标 i 的情况下可以反向遍历下标 j 计算 dp[j][i] 的值只有当 arr[j]×2arr[i] 时才满足 arr[k]arr[j] 当 arr[j]×2≤arr[i] 时不需要对当前下标 i 继续遍历更小的下标 j 。代码Python3class 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