动态规划最小化平方和

Question

我在练习考试中有这个问题,并且不知道如何解决它,所以我非常害怕决赛.无论如何,发现这个问题有一个答案将是缓解,并将帮助我理解动态编程,所以感谢阅读:)

问题:

给定n个数a1,...,a(正或负)的序列,我们希望将序列分成块,以便最小化块和的平方和,受每个块包含的约束的约束.至少2个,最多4个元素.换句话说,我们想找到1 = i [0] <i [1] <i [2] <... <i [k-1] <i [k] = n + 1来最小化(ai [0 ] + ... + ai [1] -1)^ 2 +(ai [1] + ... + ai [2] -1)^ 2 + ... +(ai [k-1] + .. .+ ai [k] -1)^ 2,这样2 <= i [1] - i [0] <= 4,2 <= i [2] - i [1] <= 4,..., 2 <= i [k] -i [k-1] <= 4.(注意,没有给出块数k.)提出O(n)时动态编程算法来解决问题.

我的问题:定义子问题.我唯一的线索是不断找到长度为4到2的最小总和,但是如果剩下1个怎么办呢？它是否加入现有的长度为2或3的组,或者是4组分组？更别说在O(n)中完成了......

Answer 1

子问题是:找到前k个数字的miminum.以下是如何将问题减少到已经解决的子问题:

我们F(k)是正方形和的最小值时解决了a1, a2, ... ak.

现在

F(2) = (a1+a2)^2
F(3) = (a1+a2+a3)^2
F(4) = min { (a1+a2+a3+a4)^2, (a1+a2)^2 + (a3+a4)^2 }
F(5) = min { (a1+a2+a3)^2 + (a4+a5)^2, (a1+a2)^2 + (a3+a4+a5)^2 }

F(n) = min {
              F(n-2) + (a[n-1]+a[n])^2,
              F(n-3) + (a[n-2]+a[n-1]+a[n])^2,
              F(n-4) + (a[n-3]+a[n-2]+a[n-1]+a[n])^2
       }

您可以编写一个简单的函数来计算F(k)以增加k的值并将它们存储在数组中.