math - Algorithm for finding the smallest number of precise squares which amount is n -

i supposed write function 1 argument n , function should count smallest number of precise squares amount n. example if n=10, function should return 2 (10=3² +1²). far have implemented solution- using dynamic programming not absolutely sure of correctness:

squares(n)   dyn[0...n]   dyn[0] <- 0     k <- 1 n        dyn[k] <- k+1        <- 1        j <- 1         while j<=k           if dyn[k-j] < dyn[k]                dyn[k] <- dyn[k-j]           <- i+1           j <- i*i        dyn[k] <- dyn[k]+1    k <- n     return dyn[n] 

please, analyze solution , if can provide faster one? far running time o(n^3/2).

you not need of this. have know math stuff.

1. some numbers squares int(sqrt(x))**2 == x
2. some numbers can represented sum of 2 squares (fermat)
3. some numbers can represented sum of 3 squares (legendre)

4. every number can represented sum of 4 squares (lagrange)

   so check first 2 conditions , if non of them holds - return 4.