algorithm - 寻找最小数量为n的精确平方的算法

我应该写一个有一个参数n的函数，这个函数应该计算最小数量的精确平方，即n。例如，如果n=10，函数应该返回2（10=32+12）到目前为止，我已经实现了一些解决方案-使用动态编程，但我并不完全确定其正确性：

Squares(n)
  dyn[0...n]
  dyn[0] <- 0

  for k <- 1 to n
       dyn[k] <- k+1
       i <- 1
       j <- 1

       while j<=k do
          if dyn[k-j] < dyn[k]
               dyn[k] <- dyn[k-j]
          i <- i+1
          j <- i*i

      dyn[k] <- dyn[k]+1
   k <- n

   return dyn[n]

请分析我的解决方案，如果你能提供更快的？到目前为止，它的运行时间是O（n3/2）。

最佳答案

你不需要这些你得知道一些数学知识。
有些数字已经是正方形了int(sqrt(x))**2 == x
一些数字可以表示为sum of 2 squares（fermat）
有些数字可以表示为sum of 3 squares（Legendre）
每个数字都可以表示为sum of 4 squares（拉格朗日）
所以只要检查前两个条件，如果没有，返回4。