Leetcode 651: 4 Keys Keyboard

 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.

Notes:

This question can be solved by dp.

Imagine that we have solved all the smaller one than i, now we need to solve dp[i].

dp[i] means the maximum number of A that can be printed.

then dp[i] can be derived from the solved dp's but with a smaller index.

If j is one of them, and dp[j] is solved, and j < i

Then dp[i] could be dp[j] * (i - j -1). Why?

Because we need to Ctr-A and Ctr-C before we can Ctr-V. For example, we have dp[3], then dp[5] could be dp[3]*(5 - 3 -1) = dp[3] (which obviously is not the optimal choice. A different way is that we can simply add two As directly (using key 1) after dp[3] which can give dp[3] + 2 for dp[5].)

Thus, in order to find the optimal choice, one way is that we can go through all the smaller ones by the above two ways:

1): use key2 + key3 + kye4s,  (this could be true for larger i), the formula for this is:

      dp[j] * (i - j -1)

2): use key1 directly, (this could be true for smaller i)

       dp[j] + (i - j)

If we decide to go through all the dp's with indexes smaller than i, then it meas the time complexity is O(N^2). In this question, N <= 50, so it should be Okay.

See the code below:

class Solution {
public:
    /**
     * @param N: an integer
     * @return: return an integer
     */
    int maxA(int N) {
        // write your code here
        vector<int> dp(N+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=N; ++i) {
            for(int j=0; j<i; ++j) {
                dp[i] = max(dp[i], dp[j] + i - j);
                if(j+3<i) dp[i] = max(dp[i], dp[j]*(i-j-1));
            }
        }
        return dp[N];
    }
};