DP笔记(17)：DP键盘打印系列，2/4键键盘
Author：zhoulujun Date：
2键/4键键盘
四键键盘
假设你有一个特殊的键盘包含下面的按键：
Key 1: (A)：在屏幕上打印一个 'A'。
Key 2: (Ctrl-A)：选中整个屏幕。
Key 3: (Ctrl-C)：复制选中区域到缓冲区。
Key 4: (Ctrl-V)：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。
现在，你只可以按键 N 次（使用上述四种按键），请问屏幕上最多可以显示几个 'A'呢？
样例 1: 输入: N = 3 输出: 3 解释: 我们最多可以在屏幕上显示三个'A'通过如下顺序按键： A, A, A
样例 2: 输入: N = 7 输出: 9 解释: 我们最多可以在屏幕上显示九个'A'通过如下顺序按键： A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
如何在 N 次敲击按钮后得到最多的 A？我们穷举呗，对于每次按键，我们可以穷举四种可能，很明显就是一个动态规划问题。
第一种思路
这种思路会很容易理解，但是效率并不高，我们直接走流程：对于动态规划问题，首先要明白有哪些「状态」，有哪些「选择」。
具体到这个问题，对于每次敲击按键，有哪些「选择」是很明显的：4 种！就是题目中提到的四个按键：A、Ctrl-A（C-A）、Ctrl-C（C-C）、和Ctrl-V（C-V）。
接下来，思考一下对于这个问题有哪些「状态」？或者换句话说，我们需要知道什么信息，才能将原问题分解为规模更小的子问题？
你看我这样定义三个状态行不行：
剩余的按键次数，用n表示；
当前屏幕上字符 A 的数量，用a_num表示；
剪切板中字符 A 的数量，用copy表示。
如此定义「状态」，就可以知道 base case：当按键次数用完时（即 n 为0），屏幕上字符A的数量（即 a_num）就是我们想要的答案。
结合刚才说的 4 种「选择」，我们可以把这几种选择通过状态转移表示出来：
状态转移：
根据每种按键操作，我们可以将状态转移表示出来：
按下A键：增加一个字符A，同时消耗1次按键次数。
新状态：dp(n - 1, a_num + 1, copy)
按下Ctrl-V(C-V)键：将剪切板中的字符A粘贴到屏幕上，同时消耗1次按键次数。
新状态：dp(n - 1, a_num + copy, copy)
按下Ctrl-A（C-A）和Ctrl-C（C-C）：全选并复制屏幕上的字符A到剪切板，同时消耗2次按键次数。
新状态：dp(n - 2, a_num, a_num)
这样可以看到问题的规模n在不断减小，肯定可以到达n = 0的 base case，所以这个思路是正确的：
function maxA(n) {
const memo = new Map();
function dp(n, a_num, copy) {
if (n <= 0) return a_num;
const key = `${n},${a_num},${copy}`;
if (memo.has(key)) return memo.get(key);
const pressA = dp(n - 1, a_num + 1, copy);
const pressCV = dp(n - 1, a_num + copy, copy);
const pressCA_CC = n > 1 ? dp(n - 2, a_num, a_num) : 0;
const result = Math.max(pressA, pressCV, pressCA_CC);
memo.set(key, result);
return result;
}
return dp(n, 0, 0);
}在这个代码中，我们使用一个递归函数 dp 来计算在剩余 n 次按键下，最大可能的字符A数量。我们用一个 memo（记忆化存储）来避免重复计算。
n 是一个明确的变量，最多为 N，但是 a_num 和 copy 可以在理论上达到非常高的值，这导致状态空间变得非常大，从而使得算法的复杂度非常高，可能会达到 O(N^3 ) 甚至更高。
为了改进这个算法，我们需要重新定义状态，以便减少状态空间和优化时间复杂度。我们可以通过将状态定义得更加抽象，专注于每一步操作时的选择和影响，从而简化问题。
第二种思路
这种思路稍微有点复杂，但是效率高。继续走流程，「选择」还是那 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。明确了这一点，可以通过这两种情况来设计算法：
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 而已，很容易得到结果：
// 按 A 键，就比上次多一个 A 而已 dp[i] = dp[i - 1] + 1;
刚才说了，最优的操作序列一定是C-A C-C接着若干C-V，所以我们用一个变量j作为若干C-V的起点。那么j之前的 2 个操作就应该是C-A C-C了
最终代码
function maxA(N) {
const dp = Array(N + 1).fill(0); // dp[0] = 0;
for (let i = 1; i <= N; i++) {
dp[i] = dp[i - 1] + 1;// 按下A键
for (let j = 2; j < i; j++) { // 按下C-A C-C组合和若干次C-V键
// 全选&复制 dp[j-2]，连续粘贴i-j次 屏幕上共 dp[j-2]*(i-j+1)个 A
dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
}
}
return dp[N];
}其中j变量减 2 是给C-A C-C留下操作数，看个图就明白了：
这样，此算法就完成了，时间复杂度 O(N^2)，空间复杂度 O(N)，这种解法应该是比较高效的了。
总结：
动态规划难就难在寻找状态转移，不同的定义可以产生不同的状态转移逻辑，虽然最后都能得到正确的结果，但是效率可能有巨大的差异。
回顾第一种解法，重叠子问题已经消除了，但是效率还是低，到底低在哪里呢？抽象出递归框架：
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,...。显然这种操作序列的结果不是最优的，但是我们并没有想办法规避这些情况的发生，从而增加了很多没必要的子问题计算。
回顾第二种解法，我们稍加思考，发现最优的序列应该是这种形式：A,A..C-A,C-C,C-V,C-V..C-A,C-C,C-V..。
根据这个事实，我们重新定义了状态，重新寻找了状态转移，从逻辑上减少了无效的子问题个数，从而提高了算法的效率。
两个键的键盘
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
示例 1：输入：3 输出：3
解释： 最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。
示例 2：输入：n = 1 输出：0
对于一个数n，他需要进行多少次的复制全部和粘贴的操作，比如25个A，最大能被25整除（比25小的数中）的数是5，那么我需要复制5个A粘贴5次就可以得到25个A，那么怎么得到5个A，最大能被5整除（比5小的数中）的数是1，因此只能通过复制一个A并粘贴5次。
当n = 1时，已经有一个A了，我们不需要其他操作，返回0
当n = 2时，我们需要复制一次，粘贴一次，返回2
当n = 3时，我们需要复制一次，粘贴两次，返回3
当n = 4时，这就有两种做法，一种是我们需要复制一次，粘贴三次，共4步，另一种是先复制一次，粘贴一次，得到AA，然后再复制一次，粘贴一次，得到AAAA，两种方法都是返回4
当n = 5时，我们需要复制一次，粘贴四次，返回5
当n = 6时，我们需要复制一次，粘贴两次，得到AAA，再复制一次，粘贴一次，得到AAAAAA，共5步，返回5
可以看出对于n，至多需要n步，即cppppp....，而如果可以分解成相同的几份，则可以减少次数，比如n=6时，目标是AAAAAA，可以分解为两个AAA或者三个AA
假设 n%m=0,n/m=min_val; m的范围[1,n-1]（总共需要输出n个A，一次复制M个，最小粘贴min_val次）
那么动态转移方程为：
dp[n]=dp[m]+（min_val-1）+1;
dp[m]代表要得到m个A最少需要多少次操作；
min_val-1代表需要对m个A进行粘贴的次数；
最后+1是复制m个A的次数。
function minSteps(n) {
const dp = new Array(n + 1).fill(0); // 创建一个长度为 n+1 的数组 dp，初始化所有元素为 0
dp[1] = 0; // dp[1] 初始化为 0，因为已经有一个 'A'
for (let i = 2; i <= n; ++i) {
let min_val = Infinity; // 初始化最小粘贴次数为无穷大
let index;
for (let j = i - 1; j >= 1; --j) {// 找出最大的能被 i 整除的 j
if (i % j === 0) {
let val = i / j;
if (val < min_val) {
min_val = val; // 最少的粘贴次数
index = j; // 在哪个位置粘贴
}
}
}
dp[i] = dp[index] + min_val - 1 + 1;// 更新 dp[i]
}
return dp[n];// 找出最大的能被 i 整除的 j
}这个如果你没有看明白。那么，为了简化问题，我们可以反过来思考：
假设我们已经有 i 个 'A'，如何获得这些 'A' 是通过一些 j 个 'A' 复制若干次得到的。
因此，我们需要找到一个 j，使得 j 个 'A' 通过粘贴操作能得到 i 个 'A'，即 i % j == 0。
更具体地：如果 i 能被 j 整除（即 i % j == 0），说明可以通过先获得 j 个 'A'，然后粘贴若干次（具体是 i / j 次）得到 i 个 'A'。
例如，假设我们要得到 i = 16 个 'A'：
我们可以通过先获得 8 个 'A'，然后粘贴一次得到 16 个 'A'。操作步骤是：
先获得 8 个 'A' 的操作次数是 dp[8]。
再粘贴一次得到 16 个 'A'，总操作次数是 dp[8] + 1。
而要获得 8 个 'A'，可以先获得 4 个 'A' 然后粘贴一次，操作次数是 dp[4] + 1。
获得 4 个 'A' 是通过先获得 2 个 'A' 然后粘贴一次，操作次数是 dp[2] + 1。
获得 2 个 'A' 是通过先获得 1 个 'A' 然后粘贴一次，操作次数是 dp[1] + 1。
通过这种方式递归地计算，我们可以找到最优的操作次数。
状态转移方程
dp[i] 表示获得 i 个 'A' 的最小操作次数。那么：
对于每个 i，我们要找到最大的 j（1 <= j < i），使得 i % j == 0。
一旦找到这个 j，可以通过 dp[j] 的操作次数，再加上从 j 到 i 的粘贴次数，即 i / j - 1 次粘贴操作（注意第一次的“复制”操作，所以加 1），总操作次数为 dp[j] + i / j。
标准动态规划代码：
function minSteps(n) {
if (n == 1) return 0;
// 对每一个格子，如果i可以被j除尽，说明j个A可以通过复制粘贴得到i个A，复制粘贴次数为i / j。
let dp = new Array(n + 1).fill(0);//到i第个A的最小操作次数
dp[1] = 0;// dp[1] 初始化为 0，因为已经有一个 'A'，1个A 不需要复制
for (let i = 2; i <= n; ++i) {// 对于每个 i 从 2 到 n，找到最大的能被 i 整除的 j，并更新 dp[i]。
for (let j = 1; j <= i / 2; ++j) {// 找出最大的能被 i 整除的 j
if (i % j == 0) {//找到可以整除的因子
dp[i] = Math.min(dp[i], dp[j] + (i / j));//状态转移
}
}
}
return dp[n];
}参考文章：
650.只有两个键的键盘（动态规划） https://blog.csdn.net/Linke66/article/details/120384747
Leetcode [650] 只有两个键的键盘 & Leetcode [651] 四键键盘 动态规划 https://www.cnblogs.com/zl1991/p/14742514.html
转载本站文章《DP笔记(17)：DP键盘打印系列，2/4键键盘》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9143.html