> For the complete documentation index, see [llms.txt](https://hswsp.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hswsp.gitbook.io/algorithm/dynamic-programming/dong-tai-gui-hua-zhi-si-jian-jian-pan.md).

# 动态规划之四键键盘

## 描述

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

key 1：（A）：在屏幕上打印一个 A

key 2：（Ctrl-A）：选中整个屏幕

key 3：（Ctrl-C）：复制选中区域到缓冲区

key 4：（Ctrl-V）：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上

现在，你只可以按键N次（使用上述四种按键），请问屏幕上最多可以显示几个A？

样例1：

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

样例2：

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

## 第⼀种思路

这种思路会很容易理解，但是效率并不⾼，我们直接⾛流程：**对于动态规划 问题，⾸先要明⽩有哪些「状态」，有哪些「选择」。**

具体到这个问题，对于每次敲击按键，**有哪些「选择」**是很明显的：4 种， 就是题⽬中提到的四个按键，分别是 `A` 、 `C-A` 、 `C-C` 、 `C-V` （ Ctrl 简 写为 C ）。 

接下来，**思考⼀下对于这个问题有哪些「状态」**？或者换句话说，我们需要知道什么信息，才能将原问题分解为规模更⼩的⼦问题？

这样定义三个状态：第⼀个状态是剩余的按键次数，⽤ `n` 表 ⽰；第⼆个状态是当前屏幕上字符 A 的数量，⽤ `a_num` 表⽰；第三个状态 是剪切板中字符 A 的数量，⽤ `copy` 表⽰。

 如此定义「状态」，就可以知道 base case：当剩余次数 n 为 0 时， a\_num 就是我们想要的答案。 

结合刚才说的 4 种「选择」，我们可以把这⼏种选择通过状态转移表⽰出来：

```python
dp(n - 1, a_num + 1, copy), # A 
解释：按下 A 键，屏幕上加⼀个字符 
同时消耗 1 个操作数 
dp(n - 1, a_num + copy, copy), # C-V 
解释：按下 C-V 粘贴，剪切板中的字符加⼊屏幕 
同时消耗 1 个操作数 
dp(n - 2, a_num, a_num) # C-A C-C 
解释：全选和复制必然是联合使⽤的， 剪切板中 A 的数量变为屏幕上 A 的数量 
同时消耗 2 个操作数
```

这样可以看到问题的规模 n 在不断减⼩，肯定可以到达 n = 0 的 base case，所以这个思路是正确的：

```python
def maxA(N: int) -> int: 
    # 对于 (n, a_num, copy) 这个状态， 
    # 屏幕上能最终最多能有 dp(n, a_num, copy) 个 A 
    def dp(n, a_num, copy): 
        # base case 
        if n <= 0: return a_num; 
        # ⼏种选择全试⼀遍，选择最⼤的结果 
        return max( dp(n - 1, a_num + 1, copy), # A 
        dp(n - 1, a_num + copy, copy), # C-V 
        dp(n - 2, a_num, a_num) # C-A C-C 
        ) 
        # 可以按 N 次按键，屏幕和剪切板⾥都还没有 A 
        return dp(N, 0, 0)
```

这个解法应该很好理解，因为语义明确。下⾯就继续⾛流程，⽤备忘录消除 ⼀下重叠⼦问题：

```python
def maxA(N: int) -> int: 
    # 备忘录 
    memo = dict() 
    def dp(n, a_num, copy): 
        if n <= 0: return a_num; 
        # 避免计算重叠⼦问题 
        if (n, a_num, copy) in memo: 
            return memo[(n, a_num, copy)] 
        memo[(n, a_num, copy)] = max( 
        # ⼏种选择还是⼀样的 
        ) 
        return memo[(n, a_num, copy)] 
    return dp(N, 0, 0)
```

这样优化代码之后，⼦问题虽然没有重复了，但数⽬仍然很多，在 LeetCode 提交会超时的。

我们尝试分析⼀下这个算法的时间复杂度，就会发现不容易分析。我们可以 把这个 dp 函数写成 dp 数组：

```python
dp[n][a_num][copy] # 状态的总数（时空复杂度）就是这个三维数组的体积
```

我们知道变量 n 最多为 N ，但是 a\_num 和 copy 最多为多少我们很难 计算，复杂度起码也有 O(N^3) 把。所以这个算法并不好，复杂度太⾼，且已经⽆法优化了。 这也就说明，我们这样定义「状态」是不太优秀的，下⾯我们换⼀种定义 dp 的思路。

## 第⼆种思路

这种思路稍微有点复杂，但是效率⾼。继续⾛流程，「选择」还是那 4 个， 但是这次我们只定义⼀个「状态」，也就是剩余的敲击次数 n 。

这个算法基于这样⼀个事实，**最优按键序列⼀定只有两种情况：**

* 要么⼀直按 A ：A,A,...A（当 N ⽐较⼩时）。&#x20;
* 要么是这么⼀个形式：A,A,...C-A,C-C,C-V,C-V,...C-V（当 N ⽐较⼤时）。

因为字符数量少（N ⽐较⼩）时， `C-A` `C-C` `C-V` 这⼀套操作的代价相对⽐较 ⾼，可能不如⼀个个按 A ；⽽当 N ⽐较⼤时，后期 `C-V` 的收获肯定很 ⼤。这种情况下整个操作序列⼤致是：开头连按⼏个`A` ，然后 `C-A` `C-C` 组合再接若⼲ `C-V` ，然后再 `C-A` `C-C` 接着若⼲ `C-V` ，循环下去。

换句话说，最后⼀次按键要么是 A 要么是 C-V 。明确了这⼀点，可以通 过这两种情况来设计算法：

```python
int[] dp = new int[N + 1];
// 定义：dp[i] 表⽰ i 次操作后最多能显⽰多少个 A 
for (int i = 0; i <= N; i++) 
`dp[i] = max( 这次按 A 键， 这次按 C-V )
```

对于「按 A 键」这种情况，就是状态 i - 1 的屏幕上新增了⼀个 A ⽽ 已，很容易得到结果：

```python
// 按 A 键，就⽐上次多⼀个 A ⽽已 
dp[i] = dp[i - 1] + 1;
```

但是，如果要按 C-V ，还要考虑之前是在哪⾥ C-A C-C 的。 刚才说了，**最优的操作序列⼀定是 C-A C-C 接着若⼲ C-V ，所以我们⽤⼀ 个变量 j 作为若⼲ C-V 的起点**。那么 j 之前的 2 个操作就应该是 C-A C-C 了：

```java
public int maxA(int N) { 
    int[] dp = new int[N + 1]; 
    dp[0] = 0; 
    for (int i = 1; i <= N; i++) { 
    // 按 A 键 
        dp[i] = dp[i - 1] + 1; 
        for (int j = 2; j < i; j++) { 
        // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次 
        // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A 
        dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1)); 
        } 
    }
    // N 次按键之后最多有⼏个 A？ 
    return dp[N]; 
}
```

其中 j 变量减 2 是给 `C-A` `C-C` 留下操作数，看个图就明⽩了：

![](/files/-May1JqyJQZqJub8D3Sg)

这样，此算法就完成了，时间复杂度 O(N^2)，空间复杂度 O(N)，这种解法 应该是⽐较⾼效的了。

## 最后总结

动态规划难就难在寻找状态转移，不同的定义可以产⽣不同的状态转移逻 辑，虽然最后都能得到正确的结果，但是效率可能有巨⼤的差异。

回顾第⼀种解法，重叠⼦问题已经消除了，但是效率还是低，到底低在哪⾥ 呢？抽象出递归框架：

```python
def dp(n, a_num, copy): 
    dp(n - 1, a_num + 1, copy), # A 
    dp(n - 1, a_num + copy, copy), # C-V 
    dp(n - 2, a_num, a_num) # C-A C-C
```

看这个穷举逻辑，是有可能出现这样的操作序列 `C-A` `C-C`，`C-A` `C-C`... 或者 `C-V`,`C-V`,... 。然这种操作序列的结果不是最优的，但是我们并没有想办法 规避这些情况的发⽣，从⽽增加了很多没必要的⼦问题计算。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hswsp.gitbook.io/algorithm/dynamic-programming/dong-tai-gui-hua-zhi-si-jian-jian-pan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.