Leetcode最长斐波那契数列

class Solution:
    
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        arr_set=set(arr)
        arr_end=len(arr)-1
        last_list=[]
        for x in range(0,arr_end-2):
            for y in range(x+1,arr_end-1):
                if arr[x]+arr[y] in arr_set:
                   last_list.append([arr[x],arr[y],arr[x]+arr[y]])
        ans=2
        if last_list==[]:
           return 0 
        while(last_list):
             ans+=1
             current_list=[]
             for each_list in last_list:
                 if each_list[-2]+each_list[-1] in arr_set:
                    each_list.append(each_list[-2]+each_list[-1]) 
                    current_list.append(each_list)             
             last_list=current_list
        return ans  
        

标准解法：
也是使用了set来加快查找速度

class Solution:
    def lenLongestFibSubseq(self, arr: list[int]) -> int:
        n = len(arr)
        arr_set = set(arr)
        dp = {}
        for k in range(1, n):
            c = arr[k]
            for j in range(k-1, -1, -1):
                b = arr[j]
                a = c - b
                if a >= b:
                    break
                if a in arr_set:
                    dp[(b, c)] = dp.get((a, b), 2) + 1
        if not dp:
            return 0
        return max(dp.values())