---

0651. 四个键的键盘

• 标签：数学、动态规划
• 难度：中等

题目链接

• 0651. 四个键的键盘 - 力扣

题目大意

描述：

假设你有一个特殊的键盘包含下面的按键：

• A：在屏幕上打印一个 'A'。
• Ctrl-A：选中整个屏幕。
• Ctrl-C：复制选中区域到缓冲区。
• Ctrl-V：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。

现在，你可以 最多 按键 $n$ 次（使用上述四种按键）。

要求：

返回屏幕上最多可以显示 'A' 的个数。

说明：

• $1 \le n \le 50$。

示例：

• 示例 1：

输入: n = 3
输出: 3
解释: 
我们最多可以在屏幕上显示三个 'A' 通过如下顺序按键：
A, A, A

• 示例 2：

输入: n = 7
输出: 9
解释: 
我们最多可以在屏幕上显示九个 'A' 通过如下顺序按键：
A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V

解题思路

思路 1：动态规划

这道题目要求在最多按键 $n$ 次的情况下，屏幕上最多可以显示多少个 'A'。

我们可以使用动态规划来解决这个问题。定义 $dp[i]$ 表示按键 $i$ 次后屏幕上最多可以显示的 'A' 的个数。

对于每次按键，有两种选择：

1. 按 A 键：屏幕上增加一个 'A'，即 $dp[i] = dp[i - 1] + 1$。
2. 使用 Ctrl-A、Ctrl-C、Ctrl-V 组合键进行复制粘贴操作：假设在第 $j$ 次按键后进行全选复制，然后连续粘贴 $i - j - 2$ 次（需要 $2$ 次按键进行全选和复制），则 $dp[i] = dp[j] \times (i - j - 1)$。

我们需要枚举所有可能的 $j$，取最大值。

算法步骤：

1. 初始化 $dp$ 数组，$dp[0] = 0$。
2. 对于 $i$ 从 $1$ 到 $n$：
   • 选择 1：按 A 键，$dp[i] = dp[i - 1] + 1$。
   • 选择 2：枚举在第 $j$ 次按键后进行全选复制（$1 \le j \le i - 2$），$dp[i] = \max(dp[i], dp[j] \times (i - j - 1))$。
3. 返回 $dp[n]$。

思路 1：代码

class Solution:
    def maxA(self, n: int) -> int:
        # dp[i] 表示按键 i 次后屏幕上最多可以显示的 'A' 的个数
        dp = [0] * (n + 1)
        
        for i in range(1, n + 1):
            # 选择 1：按 A 键
            dp[i] = dp[i - 1] + 1
            
            # 选择 2：使用复制粘贴操作
            # 枚举在第 j 次按键后进行全选复制
            for j in range(1, i - 2):
                # 需要 2 次按键进行全选和复制，剩余 i - j - 2 次按键进行粘贴
                # 粘贴 i - j - 2 次，相当于复制了 i - j - 1 份
                dp[i] = max(dp[i], dp[j] * (i - j - 1))
        
        return dp[n]

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$。需要两层循环，外层循环 $n$ 次，内层循环最多 $n$ 次。
• 空间复杂度：$O(n)$。需要使用长度为 $n + 1$ 的数组存储动态规划的状态。