⚡Flashcard Drill➔
NeetCode #718LC-873Medium2-D Dynamic Programming
← Back to All Problems

#718 · #873 · Length of Longest Fibonacci Subsequence(最长的斐波那契子序列的长度)

📌 Problem Statement & Constraints

Given a strictly increasing array arr of positive integers, return the length of the longest Fibonacci-like subsequence, in which each term equals the sum of the two preceding terms. Return 0 if no such subsequence of length at least 3 exists. Constraints: 3 <= arr.length <= 1000, 1 <= arr[i] < 2^31.

💡 Core Algorithmic Approaches

  1. dp[j][k] is the length of the longest Fibonacci-like subsequence ending with arr[j], arr[k], with j < k.
  2. If some i < j satisfies arr[i] + arr[j] == arr[k], then dp[j][k] = dp[i][j] + 1.
  3. A hash map from value to index locates i = arr[k] - arr[j] in O(1).
  4. The answer is the largest dp[j][k] that reaches at least 3, otherwise 0.

💻 Benchmark Python3 Implementation

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        index = {v: i for i, v in enumerate(arr)}
        n = len(arr)
        dp = {}                        # (j, k) -> length ending with arr[j], arr[k]
        best = 0
        for k in range(n):
            for j in range(k):
                i = index.get(arr[k] - arr[j])
                if i is not None and i < j:
                    dp[(j, k)] = dp.get((i, j), 2) + 1
                    best = max(best, dp[(j, k)])
        return best if best >= 3 else 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): every pair (j, k) is examined once with an O(1) lookup.
💾 Space Complexity
O(n^2) for the DP map in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Reading dp[(i, j)] without the default of 2: the first two terms form a length-2 seed.
  • Dropping the i < j guard: a valid Fibonacci subsequence needs the two preceding terms in order.
  • Returning best when it is below 3: the problem requires a length of at least 3, otherwise 0.
  • Assuming the array needs no index map: the value-to-index map is what makes each lookup O(1).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems