4 Keys Keyboard
Problem
Given N key strokes (A, Ctrl-A, Ctrl-C, Ctrl-V), maximize the number of A's printed.
N = 79def max_a(N):
dp = list(range(N + 1))
for i in range(7, N + 1):
for j in range(3, i - 1):
dp[i] = max(dp[i], dp[j - 1] * (i - j))
return dp[N]function maxA(N) {
const dp = Array.from({length: N + 1}, (_, i) => i);
for (let i = 7; i <= N; i++)
for (let j = 3; j < i - 1; j++)
dp[i] = Math.max(dp[i], dp[j - 1] * (i - j));
return dp[N];
}int maxA(int N) {
int[] dp = new int[N + 1];
for (int i = 0; i <= N; i++) dp[i] = i;
for (int i = 7; i <= N; i++)
for (int j = 3; j < i - 1; j++)
dp[i] = Math.max(dp[i], dp[j - 1] * (i - j));
return dp[N];
}int maxA(int N) {
vector dp(N + 1); for (int i = 0; i <= N; i++) dp[i] = i;
for (int i = 7; i <= N; i++)
for (int j = 3; j < i - 1; j++)
dp[i] = max(dp[i], dp[j - 1] * (i - j));
return dp[N];
} Explanation
We track dp[i] = the most A's we can print using exactly i key strokes. The key insight is that any good plan is "type some A's, then do one burst of select-copy-paste-paste...".
For small budgets there is nothing clever to do — just press A every time — so dp[i] = i for i up to 6.
For larger i, we guess the moment j where we last pressed a plain A. After that point we spend Ctrl-A + Ctrl-C (2 strokes) and then a run of pastes. If j is the last A-stroke, the remaining i - j strokes are pastes (after the 2-stroke copy), and each paste multiplies the current block. That gives the transition dp[i] = max(dp[i], dp[j-1] * (i-j)).
We take the best over every split point j, so the inner loop tries all the places to "stop typing and start multiplying".
Example: N = 7. The base run gives dp[6] = 6 (AAAAAA). For i = 7 the best split yields AAA then Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V → 3 · 3 = 9, so dp[7] = 9.