Build Array Where You Can Find The Maximum Exactly K Comparisons solution and explanation

MOD = 10**9 + 7

def numOfArrays(n, m, k):
    dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
    for j in range(1, m + 1):
        dp[1][j][1] = 1
    for i in range(2, n + 1):
        for j in range(1, m + 1):
            for z in range(1, k + 1):
                dp[i][j][z] = (dp[i-1][j][z] * j) % MOD
                for p in range(1, j):
                    dp[i][j][z] = (dp[i][j][z] + dp[i-1][p][z-1]) % MOD
    return sum(dp[n][j][k] for j in range(1, m+1)) % MOD

#include <vector>
using namespace std;

const int MOD = 1000000007;

int numOfArrays(int n, int m, int k) {
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(m+1, vector<int>(k+1, 0)));
    for (int j = 1; j <= m; ++j) dp[1][j][1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int z = 1; z <= k; ++z) {
                dp[i][j][z] = ((long long)j * dp[i-1][j][z]) % MOD;
                for (int p = 1; p < j; ++p) {
                    dp[i][j][z] = (dp[i][j][z] + dp[i-1][p][z-1]) % MOD;
                }
            }
        }
    }
    int totalWays = 0;
    for (int j = 1; j <= m; ++j) {
        totalWays = (totalWays + dp[n][j][k]) % MOD;
    }
    return totalWays;
}

import java.util.*;

public class Solution {
    private static final int MOD = 1000000007;
    private static int[][][] dp = new int[51][101][51];

    public int numOfArrays(int n, int m, int k) {
        for (int[][] arr2d : dp) for (int[] arr : arr2d) Arrays.fill(arr, -1);
        return numOfArraysHelper(n, m, k, 0, 0, 0);
    }

    private int numOfArraysHelper(int n, int m, int k, int index, int max, int cost) {
        if (index == n) return (cost == k) ? 1 : 0;
        if (cost > k) return 0;
        if (dp[index][max][cost] != -1) return dp[index][max][cost];

        int totalWays = 0;
        for (int i = 1; i <= m; ++i) {
            totalWays = (totalWays + numOfArraysHelper(n, m, k, index + 1, Math.max(max, i), cost + (i > max ? 1 : 0))) % MOD;
        }
        return dp[index][max][cost] = totalWays;
    }
}

const MOD = 10 ** 9 + 7;

function numOfArrays(n, m, k) {
  const dp = Array(n + 1).fill(0).map(() => Array(m + 1).fill(0).map(() => Array(k + 1).fill(-1)));

  const dfs = (i, max, z) => {
    if (i === n) return z === k ? 1 : 0;
    if (z > k) return 0;
    if (dp[i][max][z] !== -1) return dp[i][max][z];

    let ways = 0;
    for (let j = 1; j <= m; j++) {
      ways = (ways + dfs(i + 1, Math.max(max, j), z + (j > max ? 1 : 0))) % MOD;
    }
    return dp[i][max][z] = ways;
  };

  return dfs(0, 0, 0);
}

func numOfArrays(n int, m int, k int) int {
	if k == 0 {
		return 0
	}
	mod := int(1e9) + 7
	dp := make([][][]int, n+1)
	for i := range dp {
		dp[i] = make([][]int, k+1)
		for j := range dp[i] {
			dp[i][j] = make([]int, m+1)
		}
	}
	for i := 1; i <= m; i++ {
		dp[1][1][i] = 1
	}
	for i := 2; i <= n; i++ {
		for c := 1; c <= k && c <= i; c++ {
			for j := 1; j <= m; j++ {
				dp[i][c][j] = (dp[i-1][c][j] * j) % mod
				for j0 := 1; j0 < j; j0++ {
					dp[i][c][j] = (dp[i][c][j] + dp[i-1][c-1][j0]) % mod
				}
			}
		}
	}
	ans := 0
	for i := 1; i <= m; i++ {
		ans = (ans + dp[n][k][i]) % mod
	}
	return ans
}