古董键盘

示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/Uh984O
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    int mod = (int)1e9 + 7;
    public int keyboard(int k, int n) {
        int[][] C = new int[n + 1][n + 1];
        init(C);
        // dp[i][j] 表示使用 i 个单词，组成长度为j 的序列数目
        long[][] dp = new long[27][n + 1];
        for(int i = 0; i <= 26; i++){
            dp[i][0] = 1;
        }
        // dp[0][j] = 0 j != 0
        for(int i = 1; i <= 26; i++){
            for(int j = 1; j <= n; j++){
                for(int x = 0; x <= k; x++){
                    if(j - x < 0){
                        break;
                    }
                    dp[i][j] = dp[i][j] + dp[i - 1][j - x] * C[j][x];
                }
                dp[i][j] %= mod;
            }
        }
        return (int)dp[26][n];
    }
    public void init(int[][] C){
        for(int i = 1; i < C.length; i++){
            C[i][0] = 1;
            for(int j = 1; j < i; j++){
                C[i][j] = (int)(((long)C[i - 1][j - 1] + C[i - 1][j]) % mod);
            }
            C[i][i] = 1;
        }
    }
}