LeetCode 4 Keys Keyboard

Imagine you have a special keyboard with the following keys:

Key 1: (A): Prints one 'A' on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

Example 1:

Input: N = 3
Output: 3
Explanation: 
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

Input: N = 7
Output: 9
Explanation: 
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

给定四个按键，有四种操作：

• A: 打印一个字符A
• Ctrl-A: 全选
• Ctrl-C: 复制
• Ctrl-V: 粘贴

问通过n次按键操作，最多可以打印出多少个字符。

稍微分析一下，增加字符比较快的方法是用Ctrl-V，连带着需要Ctrl-C和Ctrl-A的配合，所以要想快速增加字符，必须要以Ctrl-A, Ctrl-C, Ctrl-V结尾，这就需要3个操作。当n比较小时，这3个操作相对来说比较耗时，通过分析可知，当N<=6时，直接用N次Print(A)操作能得到最多的字符。

假设dp[i]表示使用i次操作能得到的最多字符，显然dp[i]=i，当i<=6时。

当i>6时，我们可以考虑用Ctrl-A, Ctrl-C, Ctrl-V，所以结尾我们至少要空出3个操作来使用技能，也就是我们最多只能在i-3的地方开始释放Ctrl-A, Ctrl-C, Ctrl-V技能，假设释放技能的位置是b，则b<=i-3；下界是我们可以在一开始只有一个字符时使用技能，即b>=1。所以我们遍历[1,i-3]的地方释放技能，则我们可以有i-b-2个Ctrl-V结尾，再加上释放技能的位置已经有一个dp[b]了，所以总字符数是dp[b]*(i-b-1)。使用贪心策略求最大值。

完整代码如下：

class Solution {
public:
	int maxA(int N) {
		if (N <= 6)return N;
		vector<int> dp(N + 1, 0);
		for (int i = 1; i <= 6; ++i)dp[i] = i;
		for (int i = 7; i <= N; ++i) {
			for (int b = i - 3; b >= 1; --b) {
				dp[i] = max(dp[i], dp[b] + dp[b] * (i - b - 2));
			}
		}
		return dp[N];
	}
};

本代码提交AC，用时0MS。