难度: Hard
运行时间: 57 ms
内存: 16.7 MB
MOD = 10 ** 9 + 7
class Solution:
def keyboard(self, k: int, n: int) -> int:
# 用i个字母按j次，且每个字母最多按k次，总共能按出多少种内容
@cache
def dp(i, j):
if j == 0:
return 1
# 如果剩下的字母全都使用k个也无法凑出j个字母，剪枝
if i * k < j:
return 0
ret = 0
# 当前字母使用多少次
for l in range(min(j, k) + 1):
# 在j个位置中选l个位置
# 剩下(j - l)个位置用剩下的字母来填充
ret += comb(j, l) * dp(i - 1, j - l)
ret %= MOD
return ret
return dp(26, n)
此题解利用动态规划的方法解决问题。定义 dp(i, j) 为使用前 i 个字母按 j 次所能产生的不同字符串数量。基本思路是，对于每个字母，我们可以选择按 0 次到 k 次（或者直到 j 次，如果 j 较小）。通过组合数 comb(j, l) 来计算在 j 次按键中选 l 个位置按当前字母的方案数，并用剩余的 (i-1) 个字母填充剩下的 (j-l) 次按键。如果用尽所有字母也无法达到 j 次按键，则返回 0。边界情况是，如果 j 为 0（不需要按键），则有一种可能（即空字符串）。
时间复杂度: O(n * k)
空间复杂度: O(n)
MOD = 10 ** 9 + 7
class Solution:
def keyboard(self, k: int, n: int) -> int:
# dp(i, j): 使用前 i 个字母，按 j 次时的不同组合数
@cache
def dp(i, j):
if j == 0:
return 1 # 不按任何键，只有一种可能：空字符串
if i * k < j:
return 0 # 剩余字母不足以按 j 次
ret = 0
# 尝试当前字母按 0 到 k 次（不超过剩余按键数 j）
for l in range(min(j, k) + 1):
# 选择 l 个位置按当前字母，其余位置由剩余字母组成
ret += comb(j, l) * dp(i - 1, j - l)
ret %= MOD
return ret
return dp(26, n) # 从 26 个字母中选择，按键 n 次
在动态规划中，确保`dp(i, j)`的计算正确传递依赖于正确的初始化和递归关系的建立。在此题中，基本的递归关系是通过组合已知的较小问题（即使用较少的字母或较少的按键次数）来解决较大的问题。初始化特定的值确实是必需的，以确保递归有基础值可依。例如，当`j == 0`时初始化`dp(i, 0) = 1`，意味着不按任何键时，只有一种可能：空字符串。另外，当`i == 0`且`j > 0`时，应初始化为0，因为没有字母可用时不能形成任何字符串。这些初始化值确保了在进行更复杂的计算之前，基础情况已正确处理。
当`j == 0`时，`dp(i, j)`的值为1，因为不论有多少可用字母（即无论`i`的值如何），如果不需要进行任何按键操作（即`j == 0`），唯一的可能输出就是空字符串。这确实意味着对于所有的`i`值，空字符串总是一个有效的组合。这是动态规划中一个非常重要的基础情况，因为它为进一步的递归计算提供了初始条件。
在`if i * k < j`的情况下，返回值为0的逻辑基于可用资源（字母和每个字母的最大可按次数）与需求（总按键次数）的关系。这里`i * k`代表在当前考虑的字母数量下，最大可能的按键次数（即每个字母都按最大次数`k`）。如果这个最大次数还小于所需的按键次数`j`，则明显不可能形成任何有效的字符串组合，因为按键次数的需求超出了可用的按键次数上限。因此，在这种情况下返回0是合理的，表示没有有效的字符串组合可以生成。