class Solution {
public:
int keyboard(int k, int n) {
}
};
LCP 25. 古董键盘
小扣在秋日市集购买了一个古董键盘。由于古董键盘年久失修，键盘上只有 26 个字母 a~z 可以按下，且每个字母最多仅能被按 k 次。
小扣随机按了 n 次按键，请返回小扣总共有可能按出多少种内容。由于数字较大，最终答案需要对 1000000007 (1e9 + 7) 取模。
示例 1：
输入：
k = 1, n = 1输出：
26解释：由于只能按一次按键，所有可能的字符串为 "a", "b", ... "z"
示例 2：
输入：
k = 1, n = 2输出：
650解释：由于只能按两次按键，且每个键最多只能按一次，所有可能的字符串（按字典序排序）为 "ab", "ac", ... "zy"
提示：
1 <= k <= 51 <= n <= 26*k原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.9 MB, 提交时间: 2023-09-13 23:53:12
/**
* comb[i][x] 表示从i个位置中选出x个位置的组合种数
* dp[i][j] 表示前面i个位置，考虑了前j种字母组成的i长度的字符串的种数。
**/
func keyboard(k int, n int) int {
comb := make([][]int, n+1)
for i := 0; i < len(comb); i++ {
comb[i] = make([]int, n+1)
}
comb[0][0] = 1
for i := 1; i <= n; i++ {
comb[i][0] = 1
for j := 1; j <= i; j++ {
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]
}
}
dp := make([]int, n+1)
dp[0] = 1
for i := 0; i < 26; i++ {
for j := n; j >= 1; j-- {
for l := 1; l <= k; l++ {
if l > j {
break
}
dp[j] += dp[j -l] * comb[j][l]
dp[j] %= 1e9+7
}
}
}
return dp[n]
}
python3 解法, 执行用时: 104 ms, 内存消耗: 17 MB, 提交时间: 2023-09-13 23:51:16
'''
排列问题
'''
import math
from functools import lru_cache
class Solution:
def keyboard(self, k: int, n: int) -> int:
MOD = 1000000007
@lru_cache(None)
def dfs(c: int, n: int, k: int) -> int:
if n == 0:
return 1
if c <= 0:
return 0
res = 0
for i in range(0, min(n, k) + 1):
res += math.comb(n, i) * dfs(c-1, n - i, k) % MOD
return res % MOD
ans = dfs(26, n, k)
return ans % MOD
java 解法, 执行用时: 3 ms, 内存消耗: 38.7 MB, 提交时间: 2023-09-13 23:50:52
class Solution {
public static final int mod = (int)1e9 + 7;
public int keyboard(int k, int n) {
long[][] dp = new long[n + 1][27];
long[][] C = new long[26 * k + 1][k + 1];
C[0][0] = 1;
for (int i = 1; i < C.length; ++i) {
for (int j = 0; j <= Math.min(k, i); ++j) {
if (j == 0) C[i][j] = 1;
//对于j位置：当选它时 C[i - 1][j - 1], 不选j位置C[i - 1][j].
//对于j位置分析这有两种情况都有可能因此等于这两种之和。
else C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
//dp[i][j] 表示前面i个位置，考虑了前j种字母组成的i长度的字符串的种数。
// C[i][x] 表示从i个位置中选出x个位置的组合种数
for (int i = 0; i <= 26; ++i) dp[0][i] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= 26; ++j) {
for (int x = 0; x <= k && x <= i; ++x) {
dp[i][j] += dp[i - x][j - 1] * C[i][x];
}
dp[i][j] %= mod;
}
}
return (int)dp[n][26];
}
}
python3 解法, 执行用时: 88 ms, 内存消耗: 17.2 MB, 提交时间: 2023-09-13 23:48:48
'''
排列问题
'''
import math
import functools
class Solution:
def keyboard(self, k: int, n: int) -> int:
MOD = 1000000007
@lru_cache(None)
def dfs(c, n, k):
if n == 0:
return 1
if c <= 0:
return 0
res = 0
for i in range(0, min(n, k) + 1):
res += math.comb(n, i)*dfs(c-1, n - i, k) % MOD
return res % MOD
ans = dfs(26, n, k)
return ans % MOD