<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:
        # We can think of this as a graph where either Copy or Paste are the transitions
        # Each state is represented by the tuple (num_on_screen, num_copied) or (n,c)
        # Copy All: (n,c) -> (n,n)
        # Paste: (n,c) -> (n+c,c)

        # We could do a BFS from (1,0) -> (n,_)
        '''q = [(1,0)]
        dist = dict()
        dist[(1,0)] = 0
        while q:
            cur = q[0]
            s,c = cur

            if s == n:
                return dist[cur]
            
            q = q[1:]
            
            copy = (s,s)
            paste = (s+c,c)
            for action in [copy,paste]:
                if action not in dist:
                    dist[action] = dist[cur]+1
                    q.append(action)'''

        # Might be able to think about it in terms of subproblems
        # The domain of s is integers >= 1
        # The domain of c is integers >= 0
        # s >= c always! There is no way to delete characters

        # M(1,0) = 0

        # From paste:
        # M(s,s) = 1 + min{0 <= c < s} M(s,c)

        # From copy:
        # M(s,c) = 1 + M(s-c,c)

        # Subproblem dependencies:
        # We can iterate with s as rows and c as cols
        # M(s,c) = dp[s-1][c-1]

        # M(1,1)
        # M(2,1) M(2,2)
        # M(3,1) M(3,2) M(3,3)
        # M(4,1) M(4,2) M(4,3) M(4,4)
        # M(5,1) M(5,2) M(5,3) M(5,4) M(5,5)
        # M(6,1) M(6,2) M(6,3) M(6,4) M(6,5) M(6,6)

        if n == 1:
            return 0

        dp = [[1]]
        row_min = float('inf')
        for s in range(2,n+1):
            row = [float('inf')]*s
            row_min = float('inf')

            for c in range(1,s//2 + 1):
                cur = 1 + dp[s-c-1][c-1]
                row_min = min(cur, row_min)
                row[c-1] = cur
            
            row[-1] = 1 + row_min
            dp.append(row)
        
        #print(dp)

        return row_min
28073