Welcome to Subscribe On Youtube
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;
}
};
-
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; } } ############ 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; } }
-
// 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; } };
-
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
-
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 }