Minimum Cost Tree From Leaf Values LeetCode solution in JavaScript

1
var mctFromLeafValues = function (arr) {
2
  const dp = [];
3

4
  for (let i = 0; i < arr.length; i++) {
5
    dp[i] = [];
6
  }
7

8
  return treeBuilder(0, arr.length - 1);
9

10
  function treeBuilder(start, end) {
11
    if (start == end) {
12
      return 0;
13
    }
14

15
    if (dp[start][end]) {
16
      return dp[start][end];
17
    }
18

19
    let min = Number.MAX_VALUE;
20

21
    for (let i = start; i < end; i++) {
22
      const left = treeBuilder(start, i);
23
      const right = treeBuilder(i + 1, end);
24

25
      const maxLeft = Math.max(...arr.slice(start, i + 1));
26
      const maxRight = Math.max(...arr.slice(i + 1, end + 1));
27

28
      const rootVal = maxLeft * maxRight;
29

30
      min = Math.min(min, rootVal + left + right);
31
    }
32

33
    dp[start][end] = min;
34
    return min;
35
  }
36
};