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 <= 5
1 <= n <= 26*k
思路
动态规划
$dp[i][j]$表示总长度为$i$,用了前$j$种字母可能出现的字符串的数量,可以得到如下转移方程。
其中,$x$表示第$j$种字母出现的次数,其值可以为$0,1,..k$,对于每一个$x$,都有$C_i^x$种位置可以选择。
例如,$x=2$,表示第$j$种字符出现了$2$次,他可能出现在前$i$个位置中的任意两个,是一个组合问题,其结果是$C_i^2$。
C++代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!