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:
![](https://spcdn.pages.dev/leetcode/problems/1420.Build%20Array%20Where%20You%20Can%20Find%20The%20Maximum%20Exactly%20K%20Comparisons/images/e.png)
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 <= 50
1 <= m <= 100
0 <= k <= n
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| 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
}
|