小编Sto*_*ffe的帖子

问题是找到求和数n所需的最小平方数.

一些例子:

min[ 1] = 1 (1²)
min[ 2] = 2 (1² + 1²)
min[ 4] = 1 (2²)
min[13] = 2 (3² + 2²)

我知道拉格朗日的四方定理,它表明任何自然数都可以表示为四个平方的总和.

我正试图用DP解决这个问题.

这就是我提出的(不正确)

min[i] = 1 where i is a square number
min[i] = min(min[i - 1] + 1, 1 + min[i - prev]) where prev is a square number < i

什么是正确的DP方式来解决这个问题？