Kimi LeetCode LCP 25. 古董键盘 Java实现

以下是 LCP 25. 古董键盘 的 Java 实现及详细解析。---题目描述小扣在秋日市集购买了一个古董键盘。由于古董键盘年久失修键盘上只有 26 个字母 az 可以按下且每个字母最多仅能被按 k 次。小扣随机按了 n 次按键请返回小扣总共有可能按出多少种内容。由于数字较大最终答案需要对 1000000007 (1e9 7) 取模。示例- k 1, n 1 → 输出 26a z- k 1, n 2 → 输出 650ab, ac, ..., zy约束 1 k 51 n 26*k---解题思路动态规划状态定义f[i][j] 表示总共按了 i 次按键且只使用了前 j 个字母a第 j 个字母的方案数。初始状态当 i 0 时f[0][j] 1表示没有按键时无论考虑多少个字母都只有 1 种方案空串。状态转移考虑第 j 个字母的使用次数为 x0 x k且 x i- 从 f[i - x][j - 1] 的方案中新增 x 个第 j 个字母- 这 x 个字母在 i 个位置中选择位置方案数为组合数 C(i, x)所以f[i][j] \sum{x0}^{k} f[i-x][j-1] \times C(i, x)组合数计算C(m, n) 用递推方式计算避免浮点数精度问题C(m, n) \prod{k1}^{n} \frac{m - k 1}{k}注意不能写成 ret * (m - k 1) / k因为中间结果可能不是整数导致精度丢失。正确写法是 ret (m - k 1) * ret / k利用整除保证结果正确。---Java 代码javaclass Solution {private static final int MOD (int) 1e9 7;public int keyboard(int k, int n) {// f[i][j]: 按了 i 次按键使用前 j 个字母的方案数long[][] f new long[n 1][27];// 初始状态按 0 次按键无论考虑多少个字母都只有 1 种方案空串for (int j 0; j 26; j) {f[0][j] 1L;}for (int i 1; i n; i) {for (int j 1; j 26; j) {// 枚举第 j 个字母的使用次数 xfor (int x 0; x k; x) {if (i x) {// 从前 j-1 个字母、i-x 次按键的方案中// 加入 x 个第 j 个字母组合数为 C(i, x)f[i][j] f[i - x][j - 1] * c(i, x);}}f[i][j] % MOD;}}return (int) f[n][26];}/*** 计算组合数 C(m, n) m! / (n! * (m-n)!)* 使用递推方式避免精度丢失*/private long c(int m, int n) {long ret 1L;for (int k 1; k n; k) {// 注意不能写成 ret * (m - k 1) / k// 因为 (m - k 1) / k 可能除不尽导致精度丢失ret (m - k 1) * ret / k;}return ret;}}---复杂度分析维度 复杂度时间 O(n × 26 × k) O(26nk)由于 k ≤ 5实际约为 O(130n)空间 O(n × 27) O(n)---关键点总结1. 组合数计算C(i, x) 表示从 i 个位置中选择 x 个位置放置第 j 个字母这是排列组合中的经典问题。2. 整除精度组合数计算时必须使用 ret (m - k 1) * ret / k 的顺序确保每一步都是整数运算。3. 取模时机内层循环结束后统一取模避免中间结果溢出虽然 long 类型可以暂时容纳但取模是安全的好习惯。