小编yan*_*nis的帖子

我应该用一个参数编写一个函数,n函数应该计算最小数量的精确平方n.例如,如果n = 10,则函数应返回2(10 = 3 ² +1 ²).到目前为止,我已经实现了一些使用动态编程的解决方案,但我并不完全确定它的正确性:

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(n ^3/2).