Approach Framework
Explanation
We either press 'A', or press 'CTRL+A', 'CTRL+C', and some number of 'CTRL+V's. Thus, in the context of making N
keypresses to write the letter 'A' M
times, there are only two types of moves:
 Add (
1
keypress): Add1
toM
.  Multiply (
k+1
keypresses): MultiplyM
byk
, wherek >= 2
.
In the following explanations, we will reference these as moves.
Approach #1: Dynamic Programming [Accepted]
Intuition and Algorithm
Say best[k]
is the largest number of written 'A's possible after k
keypresses.
If the last move in some optimal solution of k
keypresses was adding, then best[k] = best[k1] + 1
.
Otherwise, if the last move was multiplying, then we multiplied by x
, and best[k(x+1)] = best[k(x+1)] * x
for some x < k1
.
Taking the best of these candidates lets us find best[k]
in terms of previous best[j]
, when j < k
.
Complexity Analysis

Time Complexity: . We have two nested forloops, each of which do work.

Space Complexity: , the size of
best
.
Approach #2: Optimized Dynamic Programming [Accepted]
Intuition
If we multiply by 2N
, paying a cost of 2N+1
, we could instead multiply by N
then 2
, paying N+4
. When N >= 3
, we don't pay more by doing it the second way.
Similarly, if we are to multiply by 2N+1
paying 2N+2
, we could instead multiply by N+1
then 2
, paying N+5
. Again, when N >= 3
, we don't pay more doing it the second way.
Thus, we never multiply by more than 5
.
Algorithm
Our approach is the same as Approach #1, except we do not consider multiplying by more than 5 in our inner loop. For brevity, we have omitted this solution.
Complexity Analysis

Time Complexity: . We have two nested forloops, but the inner loop does work.

Space Complexity: , the size of
best
.
Approach #3: Mathematical [Accepted]
Explanation
As in Approach #2, we never multiply by more than 5.
When N
is arbitrarily large, the long run behavior of multiplying by k
repeatedly is to get to the value . Analyzing the function at values , it attains a peak at . Thus, we should expect that eventually, best[K] = best[K5] * 4
.
Now, we need to make a few more deductions.

We never add after multiplying: if we add
c
after multiplying byk
, we should instead multiply byk+c
. 
We never add after 5: If we add
1
then multiply byk
to get to(x+1) * k = xk + k
, we could instead multiply byk+1
to get toxk + x
. Sincek <= 5
, we must havex <= 5
for our additions to not be dominated. 
The number of multiplications by 2, 3, or 5 is bounded.

Every time we've multiplied by 2 two times, we prefer to multiply by 4 once for less cost. (4^1 for a cost of 5, vs 2^2 for a cost of 6.)
 Every time we've multiplied by 3 five times, we prefer to multiply by 4 four times for the same cost but a larger result. (4^4 > 3^5, and cost is 20.)
 Every time we've multiplied by 5 five times, we prefer to multiply by 4 six times for the same cost but a larger result. (4^6 > 5^5, and cost is 30.)
Together, this shows there are at most 5 additions and 9 multiplications by a number that isn't 4.
We can find the first 14 operations on 1 by hand: 1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81
. After that, every subsequent number is achieved by multiplying by 4: ie., best[K] = best[K5] * 4
.
Complexity Analysis
 Time and Space Complexity: .
Analysis written by: @awice.