Description
You are given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:
You should build the array arr which has the following properties:
arr has exactly n integers.1 <= arr[i] <= m where (0 <= i < n).- After applying the mentioned algorithm to
arr, the value search_cost is equal to k.
Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 109 + 7.
Example 1:
Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
Example 2:
Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisfy the mentioned conditions.
Example 3:
Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]
Constraints:
1 <= n <= 501 <= m <= 1000 <= k <= n
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def numOfArrays(self, n: int, m: int, k: int) -> int:
if k == 0:
return 0
dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]
mod = 10**9 + 7
for i in range(1, m + 1):
dp[1][1][i] = 1
for i in range(2, n + 1):
for c in range(1, min(k + 1, i + 1)):
for j in range(1, m + 1):
dp[i][c][j] = dp[i - 1][c][j] * j
for j0 in range(1, j):
dp[i][c][j] += dp[i - 1][c - 1][j0]
dp[i][c][j] %= mod
ans = 0
for i in range(1, m + 1):
ans += dp[n][k][i]
ans %= mod
return ans(code-box)
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int numOfArrays(int n, int m, int k) {
if (k == 0) {
return 0;
}
long[][][] dp = new long[n + 1][k + 1][m + 1];
for (int i = 1; i <= m; ++i) {
dp[1][1][i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int c = 1; c <= Math.min(i, k); ++c) {
for (int j = 1; j <= m; ++j) {
dp[i][c][j] = (dp[i - 1][c][j] * j) % MOD;
for (int j0 = 1; j0 < j; ++j0) {
dp[i][c][j] = (dp[i][c][j] + dp[i - 1][c - 1][j0]) % MOD;
}
}
}
}
long ans = 0;
for (int i = 1; i <= m; ++i) {
ans = (ans + dp[n][k][i]) % MOD;
}
return (int) ans;
}
}(code-box)
class Solution {
public:
int numOfArrays(int n, int m, int k) {
if (k == 0) return 0;
int mod = 1e9 + 7;
using ll = long long;
vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(k + 1, vector<ll>(m + 1)));
for (int i = 1; i <= m; ++i) dp[1][1][i] = 1;
for (int i = 2; i <= n; ++i) {
for (int c = 1; c <= min(i, k); ++c) {
for (int j = 1; j <= m; ++j) {
dp[i][c][j] = (dp[i - 1][c][j] * j) % mod;
for (int j0 = 1; j0 < j; ++j0) {
dp[i][c][j] = (dp[i][c][j] + dp[i - 1][c - 1][j0]) % mod;
}
}
}
}
ll ans = 0;
for (int i = 1; i <= m; ++i) ans = (ans + dp[n][k][i]) % mod;
return (int) ans;
}
};(code-box)
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
}(code-box)
