873.md

873 Length of Longest Fibonacci Subsequence

Description

link

---

Solution 1 : DP

dp[i, j] : the answer of question before j and start from i

Recursive : dp[a, b] = dp.get((b - a, a), 2) + 1 // if b - a < a and b - a in n_set

---

Code

Complexity T : O(target * log(target)) M : O(target * log(target))

class Solution:
    def lenLongestFibSubseq(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        dp = collections.defaultdict(int)
        
        n_set = set(A)
        
        for i in range(len(A)):
            for j in range(i):
                if A[i] - A[j] < A[j] and A[i] - A[j] in n_set:
                    dp[A[j], A[i]] = dp.get((A[i] - A[j], A[j]), 2) + 1
        
        return max(dp.values() or [0])