⭐️前面的话⭐️

本篇文章将介绍力扣上的一道题【LCP 25. 古董键盘】的题解，标签：动态规划，多重背包问题，展示语言为Java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：无
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

@toc

⭐️LCP 25. 古董键盘⭐️

🔐题目详情

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

💡解题思路

解题思路： 动态规划

状态定义： 不妨定义 $f[i][j]$表示字母数(长度)为 $i$，从前 $j$个字母中进行组合得到的方案数。

确定初始状态： 当 $i==0$时， $f[0][j]=1$。

状态转移方程： 当选择第 $j$个字母时，选择该字母的数量为 $x$时 $(0<=x<=k)$，相当于在 $i-x$字符长度，从前 $j-1$个字母中选择的状态下乘以这 $x$字母在 $i$个字母中的组合，当然 $i>=x$，由于 $x$的值为 $0, 1, 2...n$，所以 $f[i][j]$的值为 $\sum_{x=0}^k f[i-x][j-1] \times C{x \choose i}$。

综上，得最终状态转移方程：

$$f[i][j]= \sum_{x=0}^k f[i-x][j-1] \times C{x \choose i}$$

🔑源代码

Java代码：

class Solution {
    private final static int MOD = (int) 1e9 + 7;
    public int keyboard(int k, int n) {
        //dp
        long[][] f = new long[n + 1][27];
        for (int j = 0; j < 27; j++) f[0][j] = 1L;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 26; j++) {
                for (int x = 0; x <= k; x++) {
                    if (i >= x) f[i][j] += f[i - x][j - 1] * c(i, x);
                }
                f[i][j] %= MOD;
            }
        }
        return (int) f[n][26];
    }
    private long c(int m, int n) {
        long ret = 1L;

        int k = 1;
        while (k <= n) {
            //注意不能写成ret *= (m - k + 1) / k;因为(m - k + 1) / k可能除不尽，计算的组合数会有错误
            ret = (m - k + 1) * ret / k;
            k++;
        }
        return ret;
    }
}

🌱总结

本题为动态规划推理题，做的方法其实很多，动态规划这一类题目最重要的就是推导三部曲（状态定义，初始状态，状态转移方程）。