<p>There is only one character <code>&#39;A&#39;</code> on the screen of a notepad. You can perform one of two operations on this notepad for each step:</p>

<ul>
	<li>Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).</li>
	<li>Paste: You can paste the characters which are copied last time.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>the minimum number of operations to get the character</em> <code>&#39;A&#39;</code> <em>exactly</em> <code>n</code> <em>times on the screen</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> Initially, we have one character &#39;A&#39;.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get &#39;AA&#39;.
In step 3, we use Paste operation to get &#39;AAA&#39;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

class Solution:
    def minSteps(self, n: int) -> int:
        '''

        Clarify:

        - We start off with an A
        - A copy uses one operation
        - you have to copy all when you copy
        - since you start with only one character, its always possible to get an answer
        - worst case perform n operations (copy paste single)

        TC 1: 'A'

        operation 1) copy
        operation 2) paste
        operation 3) paste

        TC 2: 'A'

        answer is in the range [0, n]


        brute force:

        base case: 

        if current_number_of_as > n:
            return 1000
        
        if current_number_of_as == n:
            return 0
        
        F( current_number_of_as, number_of_as_copied)

        F( current_number_of_as, number_of_as_copied ) = min(
            # copy 
            1 + F( current_number_of_as, current_number_of_as ),

            # paste what is copied (only allowed to past if number_of_as_copied != 0)
            1 + F( current_number_of_as + number_of_as_copied, number_of_as_copied )
        )

        Call the recursive function initially with F(1, 0)

        Is there an optimal substructure?:

        Let n = 8

        'AAAAAA'

        Can I get to current_number_of_as = 6, number_of_as_copied = 6 multiple times? Yes
        Paste 1 A's
        Paste 2 A's starting at 2
        Paste 3 A's starting at 3

        Optimization 1: memoize subproblems top down

        TC: O(nm), m is number of possiblities for number_of_as_copied for each respctive value in n
        SC: O(nm)

        if n == 1:
            return 0

        cache = {}

        def dp(current_number_of_a, number_of_a_copied):
            if current_number_of_a > n:
                return 1000
            if current_number_of_a == n:
                return 0
            if (current_number_of_a, number_of_a_copied) in cache:
                return cache[(current_number_of_a, number_of_a_copied)]
            
            copy = paste = 1000

            # only copy when we have not copied the current amount of a's to avoid an infinite loop 
            if current_number_of_a != number_of_a_copied:
                copy = 1 + dp(current_number_of_a, current_number_of_a)

            # paste only when there is something to paste
            if number_of_a_copied != 0:
                paste = 1 + dp(current_number_of_a + number_of_a_copied, number_of_a_copied)
            
            cache[(current_number_of_a, number_of_a_copied)] = min(copy, paste)
            return cache[(current_number_of_a, number_of_a_copied)]
    
        return dp(1, 0)


        dp(1, 0): min operations -> dp(1, 1)
        dp(1, 1): min operations -> dp(2, 1)
        dp(2, 1): min operations -> dp(2, 2), dp(3, 1)
        dp(2, 2): min operations -> dp(4, 2) return 1000
        dp(3, 1): return 0 which propogates upwards

        dp(1, 0) + dp(1, 1) + dp(2, 1) + dp(3, 1)
        =   1    +    1     +     1    +    0
        = 3
        '''

        '''
          1 2 3 4
        1 1 0 0 0
        2 2 3 0 0
        3 3 0 4 0
        4 4 4 0 5  
        

        if n == 1:
            return 0
        
        dp = [[1000 for _ in range(n)] for _ in range(n)]

        # you have to copy at the start
        dp[0][0] = 1
        
        # current_number_of_a
        for i in range(1, n):
            # number_of_a_copied
            for j in range(i):
                # paste number_of_a_copied (1000 in the case its impossible to have pasted j to get to i)     
                dp[i][j] = 1 + dp[i-(j+1)][j]
            
            # set the copy value of i to be the minimum number of operations to get to i + 1 

            dp[i][i] = 1 + min(dp[i])

        return min(dp[n-1])


          1 2 3 4
        1 1 0 0 0
        2 2 3 0 0
        3 3 0 4 0
        4   

        The key part about this problem is you can't "go back" and copy an amount less than what you currently have

        For example if you were trying to make 7 A's you could get to 6 with only 5 moves by copying and pasting 2s but you wouldn't be able to paste the remaining 1 A

        We can also optimize by reducing our "copy and paste" search space to floor(i/2) because all larger values can't copy and paste to i


        dp = [1000] * (n+1)

        dp = [1000 for _ in range(n+1)]
        dp[1] = 0

        for i in range(1, n+1):
            for j in range(1, (i//2) + 1):
                #print(i, j)
                if i%j == 0:
                    dp[i] = min(dp[i], dp[j] + i//j)
        
        print(dp)
        return dp[n]
        '''

        if n == 1:
            return 0

        cache = {}

        def dp(current_number_of_a, number_of_a_copied):
            if current_number_of_a > n:
                return 1000
            if current_number_of_a == n:
                return 0
            if (current_number_of_a, number_of_a_copied) in cache:
                return cache[(current_number_of_a, number_of_a_copied)]
            
            copy = paste = 1000

            # only copy when we have not copied the current amount of a's to avoid an infinite loop 
            if current_number_of_a != number_of_a_copied:
                copy = 1 + dp(current_number_of_a, current_number_of_a)

            # paste only when there is something to paste
            if number_of_a_copied != 0:
                paste = 1 + dp(current_number_of_a + number_of_a_copied, number_of_a_copied)
            
            cache[(current_number_of_a, number_of_a_copied)] = min(copy, paste)
            return cache[(current_number_of_a, number_of_a_copied)]
    
        return 1 + dp(1, 1)


32723