Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/651.html
Imagine you have a special keyboard with the following keys:
 A: Print one
'A'
on the screen.  CtrlA: Select the whole screen.
 CtrlC: Copy selection to buffer.
 CtrlV: Print buffer on screen appending it after what has already been printed.
Given an integer n, return the maximum number of 'A'
you can print on the screen with at most n
presses on the keys.
Example 1:
Input: n = 3 Output: 3 Explanation: We can at most get 3 A's on screen by pressing the 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
Constraints:
1 <= n <= 50
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

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]; } } } ############ class Solution { public int maxA(int n) { int[] dp = new int[n + 1]; for (int i = 0; i < n + 1; ++i) { dp[i] = i; } for (int i = 3; i < n + 1; ++i) { for (int j = 2; j < i  1; ++j) { dp[i] = Math.max(dp[i], dp[j  1] * (i  j)); } } 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]

func maxA(n int) int { dp := make([]int, n+1) for i := range dp { dp[i] = i } for i := 3; i < n+1; i++ { for j := 2; j < i1; j++ { dp[i] = max(dp[i], dp[j1]*(ij)) } } return dp[n] } func max(a, b int) int { if a > b { return a } return b }