<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:
        if n == 1:
            return 0

        # TC: O(2 ^ N); SC: O(N) - Stack Space
        # def backtrack(a, clipboard):
        #     if a > n:
        #         return float("inf")

        #     if a == n:
        #         return 0

        #     paste = 1 + backtrack(a + clipboard, clipboard)
        #     copy_paste = 2 + backtrack(a * 2, a)
        #     return min(copy_paste, paste)

        # return 1 + backtrack(1, 1)

        # TC: O(N ^ 2); SC: O(N) - Stack Space + O(N ^ 2) - Cache
        # cache = {}
        # def backtrack(a, clipboard):
        #     if a > n:
        #         return float("inf")

        #     if a == n:
        #         return 0

        #     if (a, clipboard) in cache:
        #         return cache[(a, clipboard)]

        #     paste = 1 + backtrack(a + clipboard, clipboard)
        #     copy_paste = 2 + backtrack(a * 2, a)

        #     cache[(a, clipboard)] = min(copy_paste, paste)
        #     return cache[(a, clipboard)]

        # return 1 + backtrack(1, 1)

        dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]

        dp[1][0] = 0

        for a in range(1, n + 1):
            for clipboard in range(0, a + 1):
                if a + clipboard <= n:
                    dp[a + clipboard][clipboard] = min(dp[a + clipboard][clipboard], dp[a][clipboard] + 1)

                if a * 2 <= n:
                    dp[a * 2][a] = min(dp[a * 2][a], dp[a][clipboard] + 2)

        return min(dp[n])
        



23888