Python Solution with explanation in details, easy to understand


  • 0

    If the quantity of "A" is a prime number, it can be created only by copy "A" can paste for n-1 times. So totally n times.

    If it is not a prime number, let`s say 9 "A"s,

    1. We can try to create 3 "A"s, it takes 3 steps
    2. We copy it, it takes 1 more steps
    3. We paste it for 2 times, 2 more steps.
    4. So totally 3+3 steps.

    Generally, if n = a * b, we take dp[a] steps to create a, then we will take at most dp[a]+b steps to create n "A"s

    class Solution(object):
        def minSteps(self, n):
            """
            :type n: int
            :rtype: int
            """
            dp = [None]*(n+1)
            for i in range(n+1):
                dp[i] = i
            if n == 1:
                return 0
            if n < 6:
                return dp[n]        
            for i in range(6,n+1):
                j = 2
                while j < i**0.5+1:
                    if i%j ==0:
                        dp[i] = min(dp[i],dp[i/j]+j)
                    j += 1
            return dp[n]
    

    Please let me know if you think the code above can be improved. Thank you.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.