<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 {
public:
    // int findMin(int copy, int current,int n,int** dp){
    //     if(current == n) return 0;
    //     if(copy + current > n) return -1;
    //     int& val = dp[copy-1][current-1];
    //     if(val) return val;
    //     int copying = (current == copy) ? -1 : findMin(current,current,n,dp);
    //     int pasting = findMin(copy,current+copy,n,dp);
    //     if(copying != -1 && pasting != -1) val = 1+min(copying,pasting);
    //     else if(copying == -1 && pasting == -1) val = -1;
    //     else val = 2 + copying + pasting;
    //     // cout<<val<<endl;
    //     // cout<<copy<<" "<<current<<" "<<val<<endl;
    //     return val;
    // }   
    int minSteps(int n) {
        if (n==1) return 0;
        int** dp = new int*[n];
        for(int current = n-1; current > -1; current--){
            // cout<<"Current : "<<current << endl;
            dp[current] = new int[current+1];
            for(int copy = current; copy > -1; copy--){
                int& val = dp[current][copy];
                val = -1;
                // cout<<copy<<endl;
                int copying = dp[current][current];
                int pasting = current+copy > n ? -1 : current + copy == n ? 0 : dp[current+copy][copy];
                if(copying != -1 && pasting != -1) val = 1+min(copying,pasting);
                else if(copying == -1 && pasting == -1) val = -1;
                else val = 2 + copying + pasting;
            }   
        }
        return 1+dp[1][1];
        
    }
};
77459