Topic:

Originally there was only one character ‘A’ on A notepad. You can do two things with the notepad at a time:

  1. Copy All(Copy all) : You can copy all characters in this notepad (partial copying is not allowed).
  2. Paste(Paste) : You can paste youThe last timeCopied characters.

Given a number n. You need to print exactly n ‘as’ in notepad using the minimum number of operations. Output The minimum number of operations that can print n ‘A’.

Example:

Input: 3 Output: 3 Explanation: Initially, we only had one character 'A'. Step 1, we use the Copy All operation. In step 2, we use Paste to get 'AA'. In step 3, we use Paste to get 'AAA'.Copy the code

Answer key:

I. Prime number decomposition:

After looking at the factorization of 36 ‘A’s, we see that what they want is the sum of the prime factors of 36. Prime factor means that the factor cannot be split again.

Why do we have to break it down into prime factors? Because when a factor can be factored into smaller factors, the result will be smaller. If 36 is equal to 18 times 2, is the optimal answer 18 plus 2 is equal to 20? Obviously not, because if you take 18 apart 36 is 3 times 6 times 2, you only need 3 plus 6 plus 2 times to copy and paste it. But that’s still not optimal. 36 is 3 times 2 times 3 times 2, so you only need 3 + 2 + 3 + 2 = 10 times to copy and paste. It’s already optimal.

The specific proof is to prove that m * n > m + n, equivalent to asking (m-1)*(n-1) > 1, when m and n are greater than 2, the above formula is always valid. And the code, let’s figure out what prime factors n can break down into. Let’s see if d is increasing from 2, if n is divisible by D, then D is a prime factor of n, add D to the result of copy-paste times; And if d is a prime factor, then you have to get rid of all the d’s in n at once.

class Solution { public int minSteps(int n) { int ans = 0, d = 2; while (n > 1) { while (n % d == 0) { ans += d; n /= d; } d++; } return ans; }}Copy the code

// by: negative snow Ming candle

Two: DP dynamic programming

When n is prime, like 2, 3, 5, 7, then you can only do P one by one, C first, and then n minus one P, plus the original A, n as, exactly n operations, dp[n] = n

When n is non-prime, there is the following decomposition (why later)

​ n == 8 ​ 

2 * 4: CP CPPP 6 steps

4 * 2: CPCP CP 6 steps

n == 12 ​ 

2 * 6: CP CPPCP 7 steps

6 * 2: CPPCP CP 7 steps

3 x 4: CPP CPCP 7 steps

4 * 3: CPCP PPP 7 steps

n == 16 ​ 

2 * 8: CP CPCPPP 8 steps

4 x 4: CPCP CPCP 8 steps

Why do you just have to find one group, and there won’t be smaller steps later?

The answer is no. First of all, if you look at the above factorization, you can intuitively see that each set of factorization factors ends up with the same number of steps. There is a theorem that any natural number except 0 and 1 can be written as a product of several prime numbers

If n is equal to 12, then

12 is 2 times 6 is 2 times 2 times 3

12 is 3 times 4 is 3 times 2 times 2

We can see that 12 ends up being the same prime number product 2 times 2 times 3

Dp [I] = dp[j] + dp[I/j]

For example, dp[12] = DP [6] + DP [2], which can be interpreted as follows:

If you figure out how many steps it takes to get six ACES, and then you need two of those six ACES, that’s the same thing as treating these six ACES as one ACE, and you need two

class Solution { public int minSteps(int n) { int[] dp = new int[n + 1]; for(int i = 2; i <= n; i++){ dp[i] = i; for(int j = 2; j <= Math.sqrt(i); J++) {/ / find a set of decomposed factors can break the if (I % j = = 0) {dp [I] = dp [j] + dp/I/j; break; } } } return dp[n]; }}Copy the code

/ / by: suan tou – wang – ba