## 题目描述：

LeetCode 651. 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.

## 题目大意：

```Key 1: (A): 在屏幕上打印'A'

Key 2: (Ctrl-A): 全选

Key 3: (Ctrl-C): 将选中内容复制到缓冲区

Key 4: (Ctrl-V): 将缓冲区内容粘贴在屏幕上```

## 解题思路：

dp[z][y]表示利用z次操作，缓冲区内的字符数为y时，屏幕上打印的最大字符数

```当按下字符A时：

dp[z + 1][y] = max(dp[z + 1][y], dp[z][y] + 1)

dp[z + 1][y] = max(dp[z + 1][y], dp[z][y] + y)

dp[z + 2][dp[z][y]] = max(dp[z + 2][dp[z][y]], dp[z][y])```

## Python代码：

``````class Solution(object):
def maxA(self, N):
"""
:type N: int
:rtype: int
"""
dp = collections.defaultdict(lambda : collections.defaultdict(int))
dp[0][0] = 0 #step, buffer
for z in range(N):
for y in dp[z]:
#Key 1: (A):
dp[z + 1][y] = max(dp[z + 1][y], dp[z][y] + 1)
#Key 4: (Ctrl-V):
dp[z + 1][y] = max(dp[z + 1][y], dp[z][y] + y)
#Key 2: (Ctrl-A): + Key 3: (Ctrl-C):
dp[z + 2][dp[z][y]] = max(dp[z + 2][dp[z][y]], dp[z][y])
return max(dp[N].values())
``````

Pingbacks已关闭。

1. 书影网友 发布于 2017年8月1日 14:53 #

LeetCode上还没放solution，所以又来你这里看了。
这题我有不同的做法。
dp[i] is the maximum of characters can get by using i steps
dp[i] = min( dp[i-1] + 1, dp[ii] + dp[ii] * x ),
其中x表示倍数，计算方式是 (select + copy + paste, x = i - ii - 2), 范围是 1 &amp;lt;= ii &amp;lt;= i -2.

时间复杂度是 O(n^2)。
你这个做法的时间复杂度是 O(N)吧？

2. 书影网友 发布于 2017年8月1日 14:59 #

我纠正一下对你的做法的判断:
dp[z][y], 由于y也是O(N)级别的，所以你的做法也是 O(n^2)