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
// OJ: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/
// Author: github.com/lzl124631x
// 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;
}
};