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
Solution: DP
dp[n][m][k] := ways to build given n,m,k.
dp[n][m][k] = sum(dp[n-1][m][k] + dp[n-1][i-1][k-1] – dp[n-1][i-1][k]), 1 <= i <= m
dp[1][m][1] = m
dp[n][m][k] = 0 if k < 1 or k > m or k > n
Time complexity: O(n*m^2*k)
Space complexity: O(n*m*k)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua int mem[51][101][51] = {0}; class Solution { public: int numOfArrays(int n, int m, int k) { const int kMod = 1e9 + 7; function<int(int, int, int)> dp = [&dp](int n, int m, int k) { if (k < 1 || k > m || k > n) return 0; if (n == 1 && k == 1) return m; if (mem[n][m][k]) return mem[n][m][k]; long ans = 0; for (int i = 1; i <= m; ++i) { ans += dp(n - 1, m, k); ans += dp(n - 1, i - 1, k - 1); ans -= dp(n - 1, i - 1, k); ans = (ans + kMod) % kMod; } return mem[n][m][k] = ans; }; return dp(n, m, k); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment