algorithm - 最小化平方和的动态规划

Question

我在练习考试中遇到了这个问题，但不知道如何解决，所以我很害怕期末考试。无论如何，发现这个问题有答案会让我松一口气，并且会帮助我理解动态规划，所以感谢阅读:)

问题:

Given a sequence of n numbers a1, ..., an (positive or negative), we want to divide the sequence into blocks so as to minimize the sum of the squares of the block sums, subject to the constraint that each block contains at least 2 and at most 4 elements. In other words, we want to find 1 = i[0] < i[1] < i[2] < ... < i[k-1] < i[k] = n + 1 to minimize (ai[0] + ... + ai[1]-1)^2 + (ai[1] + ... + ai[2]-1)^2 + ... + (ai[k-1] + ... + ai[k]-1)^2, such that 2 <= i[1] - i[0] <= 4, 2 <= i[2] - i[1] <= 4, ..., 2 <= i[k] - i[k-1] <= 4. (Note that the number of blocks k is not given.) Present an O(n)-time dynamic programming algorithm to solve the problem.

我的问题:定义子问题。我唯一的线索是不断地找到长度 4 到 2 的最小和，但是如果剩下 1 怎么办？它是加入现有的长度为 2 或 3 的组，还是拆分为 4 组？更不用说在 O(n) 内完成了...

Answer 1

子问题是:找到前 k 个数字的最小值。以下是如何将问题简化为已解决的子问题:

令 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 的值并将它们存储在数组中。