651 4 Keys Keyboard

651. 4 Keys Keyboard

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

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)