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

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # 基本顺序是 k，i，j 或者 A[k] = A[j] - A[i]
        n = len(A)
        dic = {}
        # 创建索引字典，提速
        for ind,val in enumerate(A):
            dic[val] = ind
        # 初始化，行代表的是i，不需要取到n-1，为了给j留出位置
        # 初始为2，只要包含了 j i 位置，则意味着已经有了2个数字。
        dp = [[2]*n for _ in range(n-1)]
        ret = 0
        for i in range(1,n):
            # j从i+1开始，毕竟j在i后面
            for j in range(i+1,n):
                diff = A[j] - A[i]
                if diff in dic and dic[diff] < i:
                    k = dic[diff]
                    dp[i][j] = dp[k][i] + 1 # 这个1，代表着k位置数字
                    ret = max(ret,dp[i][j])
        return ret