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

Question

我应该编写一个带有一个参数 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)。

Answer 1

你不需要任何这些。您必须了解一些数学知识。

1. 一些数字已经是正方形 int(sqrt(x))**2 == x
2. 一些数字可以表示为sum of 2 squares (费马)
3. 一些数字可以表示为sum of 3 squares (勒让德)

4. 每个数字都可以表示为 sum of 4 squares (拉格朗日)

   因此只需检查前两个条件，如果不满足 - 返回 4。