Question
Formatted question description: https://leetcode.ca/all/651.html
651. 4 Keys Keyboard
Imagine you have a special keyboard with the following keys:
Key 1: (A): Print one 'A' on screen.
Key 2: (CtrlA): Select the whole screen.
Key 3: (CtrlC): Copy selection to buffer.
Key 4: (CtrlV): 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 <= N <= 50
Answers will be in the range of 32bit signed integer.
Algorithm
Logical
We can analyze the examples in the question and find that N steps can print at least N A, because we can print A at every step.
Then, if you can exceed N, copy and paste must be used. Here, since selecting all and copying take up two steps, the operation to increase the number of A is actually only N2
steps, so how do we determine how many A to print, before pasting?
Actually, it’s a trade off. If you print too many or too few A, you won’t get the maximum result. So the times of printing A and pasting should be close. The easiest way is to go through all the conditions and take the maximum , The number of printing A is between [1, N3]
, the number of pasting is N2i
, plus the printed part, it is N1i
.
DP
This problem can also be done with DP. We use a onedimensional array dp, where dp[i]
represents the maximum number of A that can be printed when the total number of steps is i, initialized to N+1
, and then we decide how to find the DP formula.
For dp[i]
, the method is actually the same as the above method. It is still necessary to traverse all the number of printed A, and then multiply by the number of pasting times plus 1 to update dp[i]
.
Code
Java

public class Four_Keys_Keyboard { class Solution_logic { public int maxA(int N) { int res = N; // number of printing A is between [1, N3], // the number of pasting is N2i, // plus the printed part, it is N1i for (int i = 1; i < N  2; ++i) { res = Math.max(res, maxA(i) * (N  1  i)); } return res; } } class Solution_dp { public int maxA(int N) { //dp[i] represents the maximum number of A that can be printed when the total number of steps is i int[] dp = new int[N + 1]; dp[1] = 1; for (int i = 2; i <= N; i++) { for (int j = 1; j < i  2; j++) { dp[i] = Math.max(dp[i], dp[j] * (i  j  1)); // using copypaste } dp[i] = Math.max(dp[i], dp[i  1] + 1); // NOT using copypaste, +1 is just printing one A } return dp[N]; } } }

// OJ: https://leetcode.com/problems/4keyskeyboard/ // Time: O(N^2) // Space: O(N) // Ref: https://leetcode.com/problems/4keyskeyboard/solution/ class Solution { public: int maxA(int N) { vector<int> dp(N + 1); for (int i = 1; i <= N; ++i) { dp[i] = dp[i  1] + 1; for (int j = 2; j < i  1; ++j) dp[i] = max(dp[i], dp[i  j  1] * j); } return dp[N]; } };

class Solution: def maxA(self, n: int) > int: dp = list(range(n + 1)) for i in range(3, n + 1): for j in range(2, i  1): dp[i] = max(dp[i], dp[j  1] * (i  j)) return dp[1]
Java

public class Solution { public int maxA(int N) { int[] dp = new int[N + 1]; for (int i = 1; i <= N; i++) { dp[i] = dp[i  1] + 1; for (int j = i  3; j > 0; j) dp[i] = Math.max(dp[i], dp[j] * (i  j  1)); } return dp[N]; } }

// OJ: https://leetcode.com/problems/4keyskeyboard/ // Time: O(N^2) // Space: O(N) // Ref: https://leetcode.com/problems/4keyskeyboard/solution/ class Solution { public: int maxA(int N) { vector<int> dp(N + 1); for (int i = 1; i <= N; ++i) { dp[i] = dp[i  1] + 1; for (int j = 2; j < i  1; ++j) dp[i] = max(dp[i], dp[i  j  1] * j); } return dp[N]; } };

print("Todo!")