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: (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 <= N <= 50
Answers will be in the range of 32-bit 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 N-2 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, N-3], the number of pasting is N-2-i, plus the printed part, it is N-1-i.

DP

This problem can also be done with DP. We use a one-dimensional 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, N-3],
// the number of pasting is N-2-i,
// plus the printed part, it is N-1-i
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 copy-paste
}

dp[i] = Math.max(dp[i], dp[i - 1] + 1); // NOT using copy-paste, +1 is just printing one A
}

return dp[N];
}
}
}


• // OJ: https://leetcode.com/problems/4-keys-keyboard/
// Time: O(N^2)
// Space: O(N)
// Ref: https://leetcode.com/problems/4-keys-keyboard/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/4-keys-keyboard/
// Time: O(N^2)
// Space: O(N)
// Ref: https://leetcode.com/problems/4-keys-keyboard/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!")