Length of Longest Fibonacci Subsequence LeetCode solution in C++

1
class Solution {
2
 public:
3
  int help(int i, int j, unordered_map<int, int> &mp, vector<int> &nums, vector<vector<int>> &dp) {
4
    if (dp[i][j] != -1) return dp[i][j];
5

6
    int x = nums[i] + nums[j];
7

8
    if (mp.find(x) != mp.end()) {
9
      dp[i][j] = help(j, mp[x], mp, nums, dp);
10
      return 1 + dp[i][j];
11
    }
12

13
    return 1;
14
  }
15

16
  int solve(int idx, int n, unordered_map<int, int> &mp, vector<int> &nums,
17
            vector<vector<int>> &dp) {
18
    int maxi = INT_MIN;
19

20
    for (int i = idx; i < n; i++) {
21
      for (int j = i + 1; j < n; j++) {
22
        int x = nums[i] + nums[j];
23

24
        if (mp.find(x) != mp.end()) {
25
          maxi = max(maxi, 2 + help(j, mp[x], mp, nums, dp));
26
        }
27
      }
28
    }
29
    return (maxi == INT_MIN ? 0 : maxi);
30
  }
31
  int lenLongestFibSubseq(vector<int> &arr) {
32
    unordered_map<int, int> mp;
33
    int n = arr.size();
34
    vector<vector<int>> dp(n, vector<int>(n, -1));
35

36
    for (int i = 0; i < arr.size(); i++) mp[arr[i]] = i;
37

38
    return solve(0, n, mp, arr, dp);
39
  }
40
};