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

1
class Solution {
2
 public:
3
  int numOfArrays(int n, int m, int k) {
4
    if (m < k) return 0;
5
    int dp[2][m + 1][k + 1], mod = 1e9 + 7;
6
    memset(dp, 0, sizeof(dp));
7
    for (int j = 1; j <= m; ++j) dp[0][j][1] = j;
8
    for (int i = 1; i < n; ++i)
9
      for (int j = 1; j <= m; ++j)
10
        for (int l = 1; l <= min(i + 1, min(j, k)); ++l)
11
          dp[i & 1][j][l] =
12
              (dp[i & 1][j - 1][l] + (long)(dp[(i - 1) & 1][j][l] - dp[(i - 1) & 1][j - 1][l]) * j +
13
               dp[(i - 1) & 1][j - 1][l - 1]) %
14
              mod;
15
    return (dp[(n - 1) & 1][m][k] + mod) % mod;
16
  }
17
};