LCP 25. 古董键盘 — Python3 实现核心思路问题26 个字母每个最多按 k 次共按 n 次求能打出多少种不同的字符串。动态规划- dp[i] 表示当前已考虑的字母中构成长度为 i 的字符串的方案数。- 考虑一个新字母时假设它在最终字符串中出现 x 次0 ≤ x ≤ k- 从 i 个位置中选 x 个放该字母C(i, x)- 剩余 i-x 个位置由之前字母填充dp[i-x]- 转移new_dp[i] Σ(dp[i-x] × C(i, x))空间优化只需一维滚动数组26 次迭代即可。---完整代码可直接提交pythonclass Solution:def keyboard(self, k: int, n: int) - int:MOD 10**9 7# 预计算组合数 C[i][x]从 i 个位置中选 x 个# i 最大 n≤130x 最大 k≤5数值很小C [[0] * (k 1) for _ in range(n 1)]for i in range(n 1):C[i][0] 1for x in range(1, min(k, i) 1):C[i][x] C[i - 1][x - 1] C[i - 1][x]# dp[i]已考虑的字母中构成长度为 i 的字符串的方案数dp [0] * (n 1)dp[0] 1 # 0 种字母、长度 0只有空串 1 种for _ in range(26): # 依次考虑 26 个字母 a~znew_dp [0] * (n 1)for i in range(n 1): # 目标长度# 当前字母选 x 个x ∈ [0, min(k, i)]for x in range(min(k, i) 1):new_dp[i] (new_dp[i] dp[i - x] * C[i][x]) % MODdp new_dpreturn dp[n]---关键点说明要点 说明C(i, x) 从 i 个位置中选 x 个放当前字母用帕斯卡递推预计算滚动数组 每处理一个字母就更新一次 dp空间 O(n)初始状态 dp[0] 1表示空串其余为 0取模 每次累加后 % MOD防止溢出复杂度- 时间O(26 × n × k) ≈ O(n·k)常数很小- 空间O(n·k) 预计算组合数 O(n) DP 数组验证- k1, n1 → dp[1] 经过 26 个字母后 26 ✓- k1, n2 → 从 26 个字母选 2 个排列 26×25 650 ✓