题目链接：873. 最长的斐波那契子序列的长度
考虑到给定序列是严格递增的，而一个序列的下一个状态只跟这个序列的最后的两个元素有关。
因此记录每个数对 0 <= i < j < len(arr) 的最长的斐波那契子序列的长度。
在查找一个已有数对 (i, j) 的下一个索引时，反向查找，通过查找 arr[j] - arr[i] 是否在序列的前方来减少时间复杂度。
from collections import defaultdict
from typing import List
class Solution:
def lenLongestFibSubseq(self, arr: List[int]) -> int:
lens, idx, max_len = defaultdict(lambda: 2), {v: i for i, v in enumerate(arr)}, 0
for j in range(2, len(arr)):
for i in range(1, j):
k = arr[j] - arr[i]
if k in idx and idx[k] < i and lens[(idx[k], i)] + 1 > lens[(i, j)]:
lens[(i, j)], max_len = lens[(idx[k], i)] + 1
max_len = max(max_len, lens[(i, j)])
return max_len