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

1
class Solution {
2
  public int numOfArrays(int n, int m, int k) {
3
    int M = (int) 1e9 + 7, ans = 0;
4
    int[][] dp = new int[m + 1][k + 1]; // maximum value, num of elements seen from left side
5
    for (int i = 1; i <= m; i++) {
6
      dp[i][1] = 1; // base case
7
    }
8
    for (int i = 2; i <= n; i++) {
9
      int[][] next = new int[m + 1][k + 1];
10
      for (int j = 1; j <= m; j++) { // for the current max value
11
        for (int p = 1; p <= m; p++) { // previous max value
12
          for (int w = 1; w <= k; w++) { // for all possible k
13
            if (j > p) { // if current max is larger, update next[j][w] from dp[p][w-1]
14
              next[j][w] += dp[p][w - 1];
15
              next[j][w] %= M;
16
            } else { // otherwise, update next[p][w] from dp[p][w]
17
              next[p][w] += dp[p][w];
18
              next[p][w] %= M;
19
            }
20
          }
21
        }
22
      }
23
      dp = next;
24
    }
25
    for (int i = 1; i <= m; i++) { // loop through max that has k and sum them up.
26
      ans += dp[i][k];
27
      ans %= M;
28
    }
29
    return ans;
30
  }
31
}