algorithm - 使用动态规划将自然数表示为平方和

Question

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

一些例子:

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

我知道 Lagrange's four-square theorem它指出任何自然数都可以表示为四个平方和。

我正在尝试使用 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 方法是什么？

Answer 1

我不确定 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);
    }
}