Build Array Where You Can Find The Maximum Exactly K Comparisons LeetCode solution in JavaScript

1
var numOfArrays = function (n, m, k) {
2
  let mod = 1e9 + 7,
3
    // dp[i][c][j] the number of arrays of length i that cost c and their max element is j
4
    dp = [...Array(n + 1)].map((d) =>
5
      [...Array(k + 1)].map((d) => [...Array(m + 1)].map((d) => 0))
6
    ),
7
    // prefix[i][k][j] holds the prefix sum of dp[i][k][:j]
8
    prefix = [...Array(n + 1)].map((d) =>
9
      [...Array(k + 1)].map((d) => [...Array(m + 1)].map((d) => 0))
10
    );
11
  //basecases
12
  dp[0][0][0] = 1;
13
  prefix[0][0].fill(1);
14
  for (
15
    var i = 1;
16
    i <= n;
17
    i++ //length of array
18
  )
19
    for (
20
      var x = 1;
21
      x <= k;
22
      x++ //curcost
23
    )
24
      for (
25
        var j = 1;
26
        j <= m;
27
        j++ //curmax
28
      )
29
        // the previous max can be anything <j with a cost of x-1, to which we append j
30
        (dp[i][x][j] += prefix[i - 1][x - 1][j - 1]),
31
          // we can also append any number <=j to an array of length i-1 that already costs x,
32
          //therefore not increasing the cost
33
          (dp[i][x][j] += dp[i - 1][x][j] * j),
34
          (dp[i][x][j] %= mod),
35
          (prefix[i][x][j] = (prefix[i][x][j - 1] + dp[i][x][j]) % mod);
36
  return dp[n][k].reduce((a, c) => (a + c) % mod);
37
};