873. Length of Longest Fibonacci Subsequence

T: O(n^2)
S: O(n^2)

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 2); // sub seq len is at least 2
            map.put(arr[i], i);
        }
        int result = 0; // why from 0? ex: [1,3,5] -> can't form any seq, so it's 0
        // the number we want to form is in the later
        // so from end to front to find 2 numbers, which can make arr[i] + arr[j] = x
        for (int i = n - 3; i >= 0; i--) { 
            for (int j = n-2; j > i; j--) { // try to find from n-3 to 0, n-2 to x, to form (n-1 in map)
                int total = arr[i] + arr[j];
                if (map.containsKey(total)) {
                    dp[i][j] = dp[j][map.get(total)] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        return result;
    }
}

/**

1 2 3 5 8

if (nums[i]+nums[j] in map)
dp[i][j] = dp[j][index of nums[i]+nums[j]] + 1

T: O(n^2)
S: O(n^2)
 */