<p>Given an integer <code>n</code>, return <em>the least number of perfect square numbers that sum to</em> <code>n</code>.</p>

<p>A <strong>perfect square</strong> is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, <code>1</code>, <code>4</code>, <code>9</code>, and <code>16</code> are perfect squares while <code>3</code> and <code>11</code> are not.</p>

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

<pre>
<strong>Input:</strong> n = 12
<strong>Output:</strong> 3
<strong>Explanation:</strong> 12 = 4 + 4 + 4.
</pre>

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

<pre>
<strong>Input:</strong> n = 13
<strong>Output:</strong> 2
<strong>Explanation:</strong> 13 = 4 + 9.
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    
    int helper(vector<int>& vec, int sum, int i, int** dp) {

        if (sum == 0) return 0;
        if (sum < 0) return INT_MAX - 1;
        if (i < 0) return INT_MAX - 1;
        if (dp[i][sum]!=-1)
            return dp[i][sum];

        int k = 1 + helper(vec, sum - vec[i], i,dp);
        
        int l = helper(vec, sum, i - 1,dp);
        dp[i][sum] = min(k, l);
        return dp[i][sum];
    }

    int numSquares(int n) {
        vector<int> vec;
        int x = 2;
        float fracPow = 1.0 / (float)x;
        int val = pow(n, fracPow);
        int mod = 1e9 + 7;
        for (int i = 1; i <= val; i++) {
            vec.push_back(pow(i, x));
        }

        int len = vec.size();
        int **dp;
        dp = new int*[len+1];
        for(int i=0;i<=len;i++){
            dp[i] = new int[n + 1];
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }

        // int dp[len+1][n+1];
         for(int i=0;i<=len;i++) dp[i][0]=0;
         for(int j=0;j<=n;j++) dp[0][j]=INT_MAX-1;
         dp[0][0]=0;

         for(int i=1;i<=len;i++){
             for(int j=1;j<=n;j++){
                 if(j>=vec[i-1])
                     dp[i][j]=min(dp[i-1][j],1+dp[i][j-vec[i-1]]);
                 else
                     dp[i][j]=dp[i-1][j];
             }
         }
         return dp[len][n];

        //int minVal = 0;
        //return helper(vec, n, len - 1, dp);
    }
};
143224