Minimum Cost Tree From Leaf Values LeetCode solution in C++

1
class Solution {
2
 public:
3
  int dp[40][40] = {0};
4
  int solve(vector<int> arr, int start, int end) {
5
    if (start == end) return 0;
6
    if (dp[start][end] != 0) return dp[start][end];
7
    int mn = INT_MAX;
8
    for (int i = start; i <= end - 1; i++) {
9
      int left = solve(arr, start, i);
10
      int right = solve(arr, i + 1, end);
11
      int temp = left + right +
12
                 *max_element(arr.begin() + start, arr.begin() + i + 1) *
13
                     *max_element(arr.begin() + i + 1, arr.begin() + end + 1);
14
      mn = min(mn, temp);
15
    }
16
    return dp[start][end] = mn;
17
  }
18
  int mctFromLeafValues(vector<int> &arr) {
19
    return solve(arr, 0, arr.size() - 1);
20
  }
21
};
22
// if you like the solution plz upvote.