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

Question

问题是找到求和数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方式来解决这个问题？

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);
    }
}

Answer 2

在我看来你很亲密......

你正在拿两个术语的min(),每个术语是min[i - p] + 1p,其中p是1或其他一些正方形<i.

为了解决这个问题,只取的MIN()min[i - p] + 1在所有 p(其中p是一个正方形<i)中.

那将是一个正确的方法.可能有更快的方法.

另外,如果你给它可能会提高可读性min[]和min()不同的名称.:-)

PS上述方法要求您min[]明确地或作为DP框架的一部分进行记忆.否则,由于递归,算法的复杂性将类似于O(sqrt(n)!): - p,尽管平均情况可能要好得多.

PPS请参阅@ Nikita的答案以获得良好的实施方案.我将添加以下优化...(我不是在挑剔他的实现 - 他把它作为一个简单的.)

1. 在进入外环之前检查n是否是一个完美的正方形:如果是,min [n] = 1并且我们已经完成了.
2. 在进入内循环之前检查i是否是一个完美的正方形:如果是,min [i] = 1,并跳过内循环.
3. 如果将min [i]设置为2,则打破内循环,因为它不会变得更好(如果可以用一个方格完成,我们将永远不会进入内循环,这要归功于之前的优化).
4. 我想知道内循环上的终止条件是否可以改变以减少迭代次数,例如j*j*2 <= i或甚至j*j*4 <= i.我是这么认为的,但我还没有完全理解它.

5. 对于大i,在内循环之前计算j的限制会更快,并且在循环终止条件下将j直接与它进行比较,而不是在每个内循环迭代中对j求平方.例如

   float sqrti = Math.sqrt(i);
   for (int j = 1; j <= sqrti; ++j) {
   

   另一方面,无论如何你需要j ^ 2进行递归步骤,所以只要你存储它,你也可以使用它.