Length of Longest Fibonacci Subsequence

lcpy gen -n 873   # by problem number
lcpy gen -s length_of_longest_fibonacci_subsequence   # by problem name

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is Fibonacci-like: [1,2,3,5,8].

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest subsequence that is Fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

class Solution:
    # Time: O(n^2)
    # Space: O(n^2)
    def len_longest_fib_subsequence(self, arr: list[int]) -> int:
        index = {num: i for i, num in enumerate(arr)}
        dp: dict[tuple[int, int], int] = {}
        best = 0
        for j in range(len(arr)):
            for i in range(j):
                need = arr[j] - arr[i]
                if need < arr[i] and need in index:
                    dp[(i, j)] = dp.get((index[need], i), 2) + 1
                    best = max(best, dp[(i, j)])
        return best