Welcome to Subscribe On Youtube
650. 2 Keys Keyboard
Description
There is only one character 'A'
on the screen of a notepad. You can perform one of two operations on this notepad for each step:
 Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
 Paste: You can paste the characters which are copied last time.
Given an integer n
, return the minimum number of operations to get the character 'A'
exactly n
times on the screen.
Example 1:
Input: n = 3 Output: 3 Explanation: Initially, we have one character 'A'. In step 1, we use Copy All operation. In step 2, we use Paste operation to get 'AA'. In step 3, we use Paste operation to get 'AAA'.
Example 2:
Input: n = 1 Output: 0
Constraints:
1 <= n <= 1000
Solutions
These two keys are used to print out n A. Note that when copying, all are copied, and you cannot select parts to copy. Then copy and paste are both operation steps, ask how many steps are needed to print out n A.
For this kind of problem with obvious recurrence
characteristics, you must have a vague feeling, and you must try recursion
and DP
. Recursive solutions are generally close to brute force search, but sometimes they can be optimized to pass OJ. If recursion is not possible, then DP can be solved generally.
Another point is that for this kind of problem, finding the pattern is the most important. DP must find the state transition equation, and if the inner connection cannot be found, then the state transition equation is more difficult to write. So, start with a simple example and try to find a pattern:
When n = 1
, there is already an A, no other operations are needed, return 0
When n = 2
, need to copy
once, paste
once, return 2
When n = 3
, you need to copy
once and paste
twice, return 3
When n = 4
, there are two ways to do this,
 one is to
copy
once andpaste
three times, a total of 4 steps,  the other is to
copy
once,paste
once to get AA, thencopy
again, paste once to get AAAA, both methods return 4
When n = 5
, you need to copy
once, paste
four times, and return to 5.
When n = 6
, you need to copy
once and paste
twice to get AAA, and copy
again and paste
once to get AAAAAA
, 5 steps in total, return to 5.
By analyzing the above 6 simple examples, we can conclude some rules.
 First of all, for any n (except 1), the
worst case is to use n steps
, no more than n steps,  but it may be less than n steps. For example, when n=6, only 5 steps are used. After careful analysis, it is first spelled as AAA, and then copied and pasted to AAAAAA.
 So under what circumstances can this method be used to reduce steps? Analysis found that the
length of the small module
must bedivisible
byn
in order to be split. Forn=6
, we can actually print AA first, then copy and paste it twice, and get 5 again.
At this point in the analysis, the idea of solving the problem should be clearer, find out all the factors of n
, and then this factor
can be used as the number of modules
, and then calculate the length of the module n/i
, call recursion, and add the number of modules i To update the result res
.

class Solution { public int minSteps(int n) { int res = 0; for (int i = 2; n > 1; ++i) { while (n % i == 0) { res += i; n /= i; } } return res; } }

class Solution { public: vector<int> f; int minSteps(int n) { f.assign(n + 1, 1); return dfs(n); } int dfs(int n) { if (n == 1) return 0; if (f[n] != 1) return f[n]; int ans = n; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { ans = min(ans, dfs(n / i) + i); } } f[n] = ans; return ans; } };

class Solution: def minSteps(self, n: int) > int: @cache def dfs(n): if n == 1: return 0 i, ans = 2, n while i * i <= n: if n % i == 0: # factor `i` can be used as the number of modules # n // i, length of the module `n/i` ans = min(ans, dfs(n // i) + i) i += 1 return ans return dfs(n) ############ # iteration class Solution: def minSteps(self, n: int) > int: res = 0 i = 2 while n > 1: while n % i == 0: res += i n //= i i += 1 return res ############ """ 1. group operations as ([^C][^V][^V]...[^V]) that has in total k operations and it gets k * # of A 2. n can be written as x_1 * x_2 * ... * x_N 3. then total operations # = x_1 + x_2 + ... + x_N 4. since p * q >= p + q for integers > 1, to min the result 5. decomposite x_1 to x_N to min the sum """ ''' `yield` is a keyword that is used like return, except the function will return a generator. https://stackoverflow.com/questions/231767/whatdoestheyieldkeyworddoinpython ''' class Solution(object): def _minSteps(self, n): """ :type n: int :rtype: int """ if n == 1: return 0 for i in range(2, int((n + 1) ** 0.5) + 1): if n % i == 0: return i + self.minSteps(n / i) return n def minSteps(self, n): def factor(n): d = 2 while d * d <= n: while n % d == 0: n /= d yield d d += 1 if n > 1: yield n return sum(factor(n))

func minSteps(n int) int { f := make([]int, n+1) for i := range f { f[i] = 1 } var dfs func(int) int dfs = func(n int) int { if n == 1 { return 0 } if f[n] != 1 { return f[n] } ans := n for i := 2; i*i <= n; i++ { if n%i == 0 { ans = min(ans, dfs(n/i)+i) } } return ans } return dfs(n) }