描述

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

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 种「选择」，我们可以把这⼏种选择通过状态转移表⽰出来：

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

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

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

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

  1. def maxA(N: int) -> int: 
  2.     # 备忘录 
  3.     memo = dict() 
  4.     def dp(n, a_num, copy): 
  5.         if n <= 0: return a_num; 
  6.         # 避免计算重叠⼦问题 
  7.         if (n, a_num, copy) in memo: 
  8.             return memo[(n, a_num, copy)] 
  9.         memo[(n, a_num, copy)] = max( 
  10.         # ⼏种选择还是⼀样的 
  11.         ) 
  12.         return memo[(n, a_num, copy)] 
  13.     return dp(N, 0, 0)

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

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

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

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

第⼆种思路

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

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

  • 要么⼀直按 A ：A,A,…A（当 N ⽐较⼩时）。
  • 要么是这么⼀个形式：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 。明确了这⼀点，可以通 过这两种情况来设计算法：

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

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

  1. // 按 A 键，就⽐上次多⼀个 A ⽽已 
  2. 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 了：

  1. public int maxA(int N) { 
  2.     int[] dp = new int[N + 1]; 
  3.     dp[0] = 0; 
  4.     for (int i = 1; i <= N; i++) { 
  5.     // 按 A 键 
  6.         dp[i] = dp[i - 1] + 1; 
  7.         for (int j = 2; j < i; j++) { 
  8.         // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次 
  9.         // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A 
  10.         dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1)); 
  11.         } 
  12.     }
  13.     // N 次按键之后最多有⼏个 A？ 
  14.     return dp[N]; 
  15. }

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

image.png

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

最后总结

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

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

  1. def dp(n, a_num, copy): 
  2.     dp(n - 1, a_num + 1, copy), # A 
  3.     dp(n - 1, a_num + copy, copy), # C-V 
  4.     dp(n - 2, a_num, a_num) # C-A C-C

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