我应该编写一个带有一个参数 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 (费马)
- 一些数字可以表示为sum of 3 squares (勒让德)
每个数字都可以表示为 sum of 4 squares (拉格朗日)
因此只需检查前两个条件,如果不满足 - 返回 4。
关于寻找数量为 n 的最小精确平方数的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35278969/