题目描述
小扣在秋日市集购买了一个古董键盘。由于古董键盘年久失修,键盘上只有 26 个字母 a~z 可以按下,且每个字母最多仅能被按 k
次。
小扣随机按了 n
次按键,请返回小扣总共有可能按出多少种内容。由于数字较大,最终答案需要对 1000000007 (1e9 + 7) 取模。
样例
输入:k = 1, n = 1
输出:26
解释:由于只能按一次按键,所有可能的字符串为 "a", "b", ... "z"
输入:k = 1, n = 2
输出:650
解释:由于只能按两次按键,且每个键最多只能按一次,
所有可能的字符串(按字典序排序)为 "ab", "ac", ... "zy"
限制
1 <= k <= 5
1 <= n <= 26*k
算法
(组合数学,递推) $O(26nk)$
- 设状态 $f(i, j)$ 表示使用了 $i$ 种字母,且按了 $j$ 次键盘后的方案数。
- 初始时,$f(0, 0) = 1$,其余为 $0$。
- 转移时,对于状态 $f(i, j)$,枚举当前字母的出现次数 $u$。在 $j$ 个位置中选择 $u$ 个位置给当前字母的方案数为 $\tbinom{j}{u}$。由于组成 $j$ 个位置的过程是分步计算,所以 $f(i, j)$ 累加 $f(i - 1, j - u) \cdot \tbinom{j}{u}$。
- 最终答案为 $f(26, n)$。
时间复杂度
- 初始化组合数的时间复杂度为 $O(nk)$。
- 递推的状态数为 $O(26n)$,每次转移需要的时间为 $O(k)$。
- 故总时间复杂度为 $O(26nk)$。
空间复杂度
- 仅需要 $O(nk + 26n)$ 的额外空间存储组合数和递推数组。
- 可以通过倒序枚举 $j$ 将递推数组的空间降为 $O(n)$。
C++ 代码
#define LL long long
class Solution {
public:
int keyboard(int k, int n) {
const int mod = 1000000007;
vector<vector<LL>> C(n + 1, vector<LL>(k + 1));
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= min(i, k); j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
vector<vector<LL>> f(27, vector<LL>(n + 1, 0));
f[0][0] = 1;
for (int i = 1; i <= 26; i++)
for (int j = 0; j <= n; j++)
for (int u = 0; u <= min(k, j); u++)
f[i][j] = (f[i][j] + f[i - 1][j - u] * C[j][u]) % mod;
return f[26][n];
}
};
C++ 代码(空间优化)
#define LL long long
class Solution {
public:
int keyboard(int k, int n) {
const int mod = 1000000007;
vector<vector<LL>> C(n + 1, vector<LL>(k + 1));
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= min(i, k); j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
vector<LL> f(n + 1, 0);
f[0] = 1;
for (int i = 1; i <= 26; i++)
for (int j = n; j >= 0; j--)
for (int u = 1; u <= min(j, k); u++)
f[j] = (f[j] + f[j - u] * C[j][u]) % mod;
return f[n];
}
};