title: Algorithm for finding the smallest number of precise squares which amount is n
body: <p>I am supposed to write a function with one argument <code>n</code> and the function should count the smallest number of precise squares which amount is <code>n</code>. For example if n=10, the function should return 2 (10=3<sup>2</sup> +1<sup>2</sup>). So far i have implemented some solution- using dynamic programming but I am not absolutely sure of its correctness:</p>
  
  <pre><code>Squares(n)
    dyn[0...n]
    dyn[0] &lt;- 0 
  
    for k &lt;- 1 to n
         dyn[k] &lt;- k+1
         i &lt;- 1
         j &lt;- 1
  
         while j&lt;=k do
            if dyn[k-j] &lt; dyn[k]
                 dyn[k] &lt;- dyn[k-j]
            i &lt;- i+1
            j &lt;- i*i
  
        dyn[k] &lt;- dyn[k]+1
     k &lt;- n
  
     return dyn[n]
  </code></pre>
  
  <p>Please, analyze my solution and if you can provide faster one? So far its running time is O(n<sup>3/2</sup>).</p>