Problem
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 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 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 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]
Constraints:
1 <= n <= 50
1 <= m <= 100
0 <= k <= n
Solution
/**
* @param {number} n
* @param {number} m
* @param {number} k
* @return {number}
*/
var numOfArrays = function(n, m, k) {
return helper(n, m, k, 0, {});
};
var helper = function (n, m, k, maxSoFar, dp) {
if (n === 0 && k === 0) return 1;
if (n === 0) return 0;
if (maxSoFar === m && k > 0) return 0;
var key = `${n}-${k}-${maxSoFar}`;
if (dp[key] !== undefined) {
return dp[key];
}
var mod = Math.pow(10, 9) + 7;
var ans = 0;
// choose num less than the current max value
for (var i = 1; i <= maxSoFar; i++) {
ans = (ans + helper(n - 1, m, k, maxSoFar, dp)) % mod;
}
// choose num bigger than the current max value
for (var j = maxSoFar + 1; j <= m; j++) {
ans = (ans + helper(n - 1, m, k - 1, j, dp)) % mod;
}
dp[key] = ans;
return dp[key];
};
Explain:
nope.
Complexity:
- Time complexity : O(n * m ^ 2 * k).
- Space complexity : O(n * m * k).