Formatted question description: https://leetcode.ca/all/1420.html
1420. Build Array Where You Can Find The Maximum Exactly K Comparisons (Hard)
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 exactlyn
integers.1 <= arr[i] <= m
where(0 <= i < n)
.- After applying the mentioned algorithm to
arr
, the valuesearch_cost
is equal tok
.
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 10^9 + 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 satisify 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]
Example 4:
Input: n = 50, m = 100, k = 25 Output: 34549172 Explanation: Don't forget to compute the answer modulo 1000000007
Example 5:
Input: n = 37, m = 17, k = 7 Output: 418930126
Constraints:
1 <= n <= 50
1 <= m <= 100
0 <= k <= n
Related Topics:
Dynamic Programming
Solution 1. DP
// OJ: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/
// Time: O(M^2 * NK)
// Space: O(MNK)
// Ref: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/discuss/586576/C%2B%2B-Bottom-Up-Dynamic-Programming-with-Explanation
class Solution {
typedef long long LL;
LL dp[51][101][51] = {};
public:
int numOfArrays(int n, int m, int k) {
int mod = 1e9+7;
for (int i = 0; i <= m; ++i) dp[1][i][1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int t = 1; t <= k; ++t) {
LL s = 0;
s = (s + j * dp[i - 1][j][t]) % mod;
for (int x = 1; x < j; ++x) s = (s + dp[i - 1][x][t - 1]) %mod;
dp[i][j][t] = (dp[i][j][t] + s) % mod;
}
}
}
LL ans = 0;
for (int i = 1; i <= m; ++i) ans = (ans + dp[n][i][k]) % mod;
return ans;
}
};
Java
class Solution {
public int numOfArrays(int n, int m, int k) {
final int MODULO = 1000000007;
int[][][] dp = new int[n + 1][m + 1][k + 2];
dp[0][0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
for (int p = 0; p <= k; p++) {
for (int q = 1; q <= m; q++) {
if (q > j)
dp[i + 1][q][p + 1] = (dp[i + 1][q][p + 1] + dp[i][j][p]) % MODULO;
else
dp[i + 1][j][p] = (dp[i + 1][j][p] + dp[i][j][p]) % MODULO;
}
}
}
}
int count = 0;
for (int i = 1; i <= m; i++)
count = (count + dp[n][i][k]) % MODULO;
return count;
}
}