# 651     4 Keys Keyboard

## 651. [4 Keys Keyboard](https://leetcode.com/problems/4-keys-keyboard/description/)

## 1. Question

Imagine you have a special keyboard with the following keys:

`Key 1: (A)`: Print 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.

## 2. Implementation

**(1) DP**

思路: 根据题意可知，对于每次的操作，我们可以直接打印或者复制，如果我们完全没不复制，则我们最多可以打印n个A, 如果我们要复制，则需要预留3个步骤给 Ctrl A + Ctrl C + Ctrl V，

dp\[i]表示在第i步时，我们可以得到最多的A的个数，通过上面分析，dp\[i] 至少为i，在总操作数为i的情况下，我们尝试找出步数j，j为打印A的次数，那么剩余的步数 (i - j - 1)则是执行 Ctrl V的次数, 显然j的范围在 【1, i - 3】, 正如之前说所，i - 3是因为要预留3步给 Ctrl A + Ctrl C + Ctrl V

```java
class Solution {
    public int maxA(int N) {
        int[] dp = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            dp[i] = i;
            for (int j = 1; j <= i - 3; j++) {
                dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
            }
        }
        return dp[N];
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n ^ 2), 空间复杂度O(n)