[DP]4键键盘

题目介绍

题目来自：651. 4键键盘

意思就是给定一个数字，作为你操作的次数，其中每一次的操作有四种选择

1. 键盘按下A键，文本多加一个A字
2. 键盘同时按Ctrl+A键，当前所有文本选中
3. 键盘同时按Ctrl+C键，当前文本复制到剪贴板上
4. 键盘同时按Ctrl+V键，当前文本粘贴到文本上

要求，对于给定的操作数n，求n个操作最多能产生几个“A”？

问题的识别和思考

题目给出了两个信息

1. 每一步都有4个选择
2. 求最值

这种状态和选择的组合，暗示了解决问题可以从动态规划开始考虑。

如果使用动态规划的话，就开始着手动态规划的几个关键要素的确定

确定DP数组和状态

确定DP数组，关键在于如何正确的定义每一个状态，因为如果使用dp数组的话，每一个dp[i]都代表着给定一个数字i，就能从dp[i]中获取一个答案。

这个问题的状态是什么？也就是说，每一次操作的执行，什么在改变？

每一次的操作，文本上的A的个数都在改变，比如我按下一个A，很明显文本上就多出来一个A。那么我可以定义dp数组表示：

当敲击执行第i次的操作时候，文本上出现最多的A字符的个数为dp[i]个

状态是如何转移的

假设我们身处第i次操作的状态上，我们下一次的操作，决定了i+1次操作，是如何改变状态的。

其实这里有两种情况可以改变dp[i+1]的值。

1. 在第i处，按下A键，$dp[i+1] = dp[i]+1$，文本上多出了一个A
2. 在第i处，按下Ctrl-V，剪贴板里面的内容全部粘贴出去。

注意：在i处按下全选/复制是不会改变A的个数值的，所以这里并没有改变任何状态。

现在最复杂的就是按下Ctrl-V粘贴之后情况的处理。

粘贴的内容来自哪里？

粘贴的内容来自于上一次按下”全选-复制“这个组合的时候。当然对于每一个状态i来说，在他前面的所有状态[0~i]处，每一处都会发生两个状态的选择。这个组合是有很多种的，如下图

前两种就是i之前的几种常规的状态，可见，第一行这种情况，最后会产生八个A，第二行同样也是，但是第三种和第四种就只有5和0个A，这两种很明显在任何情况下都不会是出现A最多的选择。

现在回答标题的问题，”粘贴的内容来自哪里“？，其实比较难以发现的是，这道题全选和复制必须结合在一起使用，为了达到产出A最多的目的，否则全选和复制任何一个操作单独独立出来，即便重复10086遍也是无用功。

而粘贴的内容，就来自于上一次的”全选-复制“这个组合发生的地方。比如在上面图中的红色块内。当全选和复制这个动作组合结束的时候，剪贴板里的内容就是4个A，那么在最后的黄色块”粘贴“动作执行之后，全文将出现8个A。

最优子结构和状态转移

要想解决DP问题，必须要解决这个最优子结构的问题，也就是，当前i这个状态的结果，如何从前一个/前n个转态的结果经过递推和验算得到的。

我们站在i这个位置上，我未来的路由两个选择，一个是去粘贴，一个是去按A，但是我本身也不确定我”粘贴“的本钱——”剪贴板现存的A“到底有多少。而剪贴板现存的A有多少取决与”全选-复制“这个组合发生的地方在哪里，正如上图的红色块，如果红色块”不幸“发生在了3、4行这种情况下，就算之后粘贴再多遍也无济于事。

其实我们可以现在隐隐约约的得到两个规律

1. 前期最好是多按A，就像打moba类游戏需要发育一样。
2. 后期最好是多按Ctrl-V，因为随着可操作的次数越来越少，剪贴板再粘贴不出去就来不及了。

而我们想要得知的，就是如何安排这个a的大小和n的大小。并且这里思维不要固定死了，这个a并不是一步一步+1，依靠按下A来得到的，a也可以通过复制粘贴之后接着全选再复制，然后再粘贴… 这样说比较啰嗦，看图。

看到两个红色块了吗？上面的文字描述就是这个意思。在最后的i到达之前，前面的这种全选复制的红色块可以出现很多次。

是不是得到规律之后反而觉得思路更加乱了？

不要灰心，继续分析。当我们处在i状态的时候，设置一个j，从前往后遍历，从头开。每一个j遍历的循环内，都把这个j前两个格子当做执行”全选-复制“组合。看图，注意j的位置。

想象这两个红色块从前往后移动。这个移动的过程代表什么？——在移动之前，我们知道dp[j-2]处的值，代表全选复制之前，0~j-2范围内的最多A，假设这个数字为a，接下去我们应该怎么样操作才能使得这个数字不断的变大？

当然是把$a$全选-复制过来粘贴很多次！，我们需要先全选复制之后，然后不断的粘贴，在剩下有限的操作内放大这个数字。

当然在红色移动的过程中，总有一个合适的位置使得整个 先积累再全选-复制最后粘贴很多次 的过程得到的结果是最大的。所以我们需要迭代一个数字，更新这个max值。代码可以如下书写：

 dp[i] = Math.max(dp[i],dp[j-2]*(i-j+1));

这个dp[i]是我们每一个状态需要求的值，上面这个式子就可以通过不断的移动j，得到状态i下最多的A数量。

直到这个红色块移动到i的位置。这样我们就已经得到了i状态下的0~i范围内，通过操作获得的最多A数字。

BaseCase的讨论

这个算法的basecase其实可以讨论的内容比较少，根据dp数组定义，当我什么都不做，即dp[0]的时候，其实无论如何A都是无法产出的。

所以dp[0]不需要设置什么值，初始化就是0，另外这里也提醒了我们：

1. 当我们需要知道n个操作产生的最多A，我们需要去dp[n]去寻找答案，那么我们的数组就要设置为 int[] dp = new int[N+1];
2. 另外，遍历的时候，为了防止溢出访问到dp[-1]，我们也直接跳过0，让i从1开始遍历到n（<=n）

代码实现

public int maxA(int N){
    //操作第i次，此时A的个数有多少
    int[] dp = new int[N+1];
    for (int i = 1; i <= N; i++) {
        dp[i] = dp[i-1]+1;
        for (int j = 2; j < i; j++) {
            dp[i] = Math.max(dp[i],dp[j-2]*(i-j+1));
        }
    }
    return dp[N];
}

总结

这道题是一道mid题，虽然代码很少，但是一些递推的还是很难想的，就比如：

1. ”全选-复制“这两个操作成对出现才会使得操作组合有产出”最长A“的机会，这个很难想到。
2. 另外，在关系递推的时候，一定要反复告诉自己要使用”数学归纳“的思想，当我们想要递推f(k+1)的时候，要反复告诉自己f(k)的答案是知道的。
3. 这个代码的结构值得细细品味：
   1. 外层for循环，可以根据前面i-1的最值得到一个状态的转换之后的结果
   2. 内层for循环，将这个结果拿去和先积累再全选-复制最后粘贴很多次 这个模式得到的结果拿去比较，最后得到一个最值作为状态i的结果。