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
dp[j][k]is the length of the longest Fibonacci-like subsequence ending witharr[j], arr[k], withj < k.- If some
i < jsatisfiesarr[i] + arr[j] == arr[k], thendp[j][k] = dp[i][j] + 1. - A hash map from value to index locates
i = arr[k] - arr[j]in O(1). - 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 < jguard: a valid Fibonacci subsequence needs the two preceding terms in order. - Returning
bestwhen 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.