Minimum Score Triangulation of Polygon LeetCode solution in JavaScript

1
var minScoreTriangulation = function (values) {
2
  let dp = Array(values.length)
3
    .fill()
4
    .map((i) => Array(values.length).fill(0));
5
  function dfs(i, j) {
6
    if (dp[i][j]) return dp[i][j];
7
    if (j - i < 2) return 0;
8
    let min = Infinity;
9
    // k forms a triangle with i and j, thus bisecting the array into two parts
10
    // These two parts become two subproblems that can be solved recursively
11
    for (let k = i + 1; k < j; k++) {
12
      let sum = values[i] * values[j] * values[k] + dfs(i, k) + dfs(k, j);
13
      min = Math.min(min, sum);
14
    }
15
    return (dp[i][j] = min);
16
  }
17
  return dfs(0, values.length - 1);
18
};