LCP 25. 古董键盘 — Rust 实现核心思路- 状态dp[i] 表示已考虑的字母中构成长度为 i 的字符串的方案数。- 转移每引入一个新字母假设它在字符串中出现 x 次0 ≤ x ≤ k- 从 i 个位置选 x 个放该字母C(i, x)- 剩余 i-x 个位置由之前字母填充dp[i-x]- 滚动26 个字母依次处理一维数组滚动更新。---完整代码可直接提交rustimpl Solution {pub fn keyboard(k: i32, n: i32) - i32 {const MOD: i64 1_000_000_007;let k k as usize;let n n as usize;// 1. 预计算组合数 C[i][x]从 i 个位置选 x 个// i 最大 130x 最大 5数值很小let mut c vec![vec![0i64; k 1]; n 1];for i in 0..n {c[i][0] 1;let max_x k.min(i);for x in 1..max_x {c[i][x] (c[i - 1][x - 1] c[i - 1][x]) % MOD;}}// 2. dp[i]已考虑字母中构成长度为 i 的方案数let mut dp vec![0i64; n 1];dp[0] 1; // 空串// 3. 依次处理 26 个字母for _ in 0..26 {let mut new_dp vec![0i64; n 1];for i in 0..n {let max_x k.min(i);for x in 0..max_x {new_dp[i] (new_dp[i] dp[i - x] * c[i][x]) % MOD;}}dp new_dp;}dp[n] as i32}}---关键点说明要点 说明i64 中间计算 防止乘法溢出最后转 i32 返回帕斯卡递推 C[i][x] C[i-1][x-1] C[i-1][x]预计算避免重复求组合数滚动数组 每处理一个字母就生成新的 new_dp空间 O(n)取模时机 组合数预计算和 DP 转移时都 % MOD保证不溢出复杂度- 时间O(26 × n × k) ≈ O(n·k)其中 n ≤ 130, k ≤ 5- 空间O(n·k) 组合数表 O(n) DP 数组
