Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

A keyboard with only two keys

Topic describes

Originally the notepad had A single character ‘A’. You can do two things with the notepad at a time:

Copy All: Copies All characters in this notepad (not only some characters). Paste: pastes the characters that were copied last time. Given the number n, you need to print exactly n ‘A’ in notepad using the minimum number of operations. Returns the minimum number of operations that can print n ‘A’.

When I first read this problem, I felt it should be dynamic programming, but I could not find the state transition equation. When I saw the solution, I still felt very sorry, just a little bit.

1. Thoughts and ideas

There are only two operations, copy and paste, where copy must make A copy of everything.

Minimum number of times, copy all, these two give me greedy feeling at the beginning, for n A, it expects the last operation to be n/2 all copy and paste, n/2 is n/4… And so on, you get the smallest degree. But I soon discovered a flaw in this idea. For example, if n is 15 at this point, the pattern n/2->n/4 will not work.

15 = 3 * 5 although 15 cannot be obtained by the above mode, it can be obtained by the operation of factor 3. But unfortunately I’m not thinking about prime factors here.

Analysis to the above, then the implementation of the problem is simple:

  • For a prime number, it cannot accelerate it by any factors, so its operand is itself
  • For composite numbers, it could be accelerated by factors, but struggling to figure out the transition equation for dynamic programming, I chose to build a store from start to finish[1,n]The array value is the minimum operand.

1.1 Algorithm Flow

  • freq[1-n]The values are successively assigned to1-n, modifyfreq[1] = 0
  • traverse2-nIs less than or equal to for each traversal updatenThe minimum number of all multiples of
  • When all traversal is complete, returnfreq[n]

1.2 code

def minSteps(n) :
    freq = [x for x in range(n + 1)]
    freq[1] = 0
    for i in range(2, n + 1):
        j = 2
        tmp = i * j
        while tmp <= n:
            # Update the current multiples of I
            freq[tmp] = min(freq[i] + j, freq[tmp])
            j += 1
            tmp = i * j
    return freq[n]
Copy the code

2. Official solution

2.1 Dynamic Planning

F [I] represents the minimum number of operations to print A of I.

For I, we should first have J A’s, use A copy operation, and then use several paste operations to get I

So j should be a factor of I, and the number of pastes is I over j-1.

State transition equation: F [I] = min(f[j] + I/j) J is a factor of I

def minSteps(n) : 
    freq = [0] * (n + 1)
    for i in range(2, n + 1):
        freq[i] = float("inf")
        j = 1
        while j * j <= i:
            if i % j == 0:
                # State transition
                freq[i] = min(freq[i], freq[i // j] + j)
                freq[i] = min(freq[i], freq[j] + i // j)
            j += 1
    return freq[n]
Copy the code

2.2 Prime factorization

The state transition equation of the dynamic programming above is as follows: F [I] = min(f[j] + I/j) (j is a factor of I)

Also equivalent to: f[I] = min(f[I/j] + j) (j is a factor of I)

So the problem becomes: given an initial value of n, we want to do a number of operations to change it to 1. Each operation we can take a factor j of n greater than 1, cost j and reduce n to n/j. In all possible sequences of operations, the minimum of the total cost is freq[n]. It’s essentially the prime factorization of n, taking the sum of all the prime factors.

def minSteps(n) : 
    ans = 0
    i = 2
    # Factor prime factors
    while i * i <= n:
        while n % i == 0:
            ans += i
            n //= i
        i += 1

    if (n > 1):
        ans += n
    return ans
Copy the code