-
Notifications
You must be signed in to change notification settings - Fork 243
/
7th October LeetCode Solution.cpp
38 lines (34 loc) · 1.17 KB
/
7th October LeetCode Solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int numOfArrays(int n, int m, int k) {
constexpr int kMod = 1'000'000'007;
// dp[i][j][k] := # of ways to build an array of length i, where j is the
// Max used num and k is the search_cost
vector<vector<vector<int>>> dp(
n + 1, vector<vector<int>>(m + 1, vector<int>(k + 1)));
for (int j = 1; j <= m; ++j)
dp[1][j][1] = 1;
for (int i = 2; i <= n; ++i) // For each length
for (int j = 1; j <= m; ++j) // For each max value
for (int cost = 1; cost <= k; ++cost) { // For each cost
// 1. appending any of [1, j] in i-th position
// doesn't change the max and cost
dp[i][j][cost] = static_cast<long>(j) * dp[i - 1][j][cost] % kMod;
// 2. appending j in i-th position
// make j the new max and cost 1
for (int prevMax = 1; prevMax < j; ++prevMax) {
dp[i][j][cost] += dp[i - 1][prevMax][cost - 1];
dp[i][j][cost] %= kMod;
}
}
int ans = 0;
for (int j = 1; j <= m; ++j) {
ans += dp[n][j][k];
ans %= kMod;
}
return ans;
}
};
//Leetcode POTD
//CPP
//7th Oct