使用动态编程将自然数表示为平方和

使用动态编程将自然数表示为平方和

我不确定DP是否是解决此问题的最有效方法，但是您要求使用DP。

min [i] = min（min [i-1] +1，1 + min [i-prev]）其中prev是一个平方数 <i
这很接近，我将条件写为

min[i] = min(1 + min[i - prev]) for each square number 'prev <= i'

请注意，

i

您需要分别检查的不同可能值

prev

。

这是Java的简单实现。

Arrays.fill(min, Integer.MAX_VALUE);min[0] = 0;for (int i = 1; i <= n; ++i) {    for (int j = 1; j*j <= i; ++j) {        min[i] = Math.min(min[i], min[i - j*j] + 1);    }}