最小平方和的动态规划
最小平方和的动态规划
提问于 2011-12-15 06:59:30
我在练习考试上有这个问题，不知道怎么解决，所以我很害怕期末考试。无论如何，如果发现这个问题有一个答案，就会减轻我的负担，并帮助我理解动态编程，因此，谢谢您的阅读:)
问题：
给出了n个数的序列a1，.，a(正或负)，我们要把序列划分成块，以便使块和的平方和最小，但每个块至少包含2个元素，最多包含4个元素。换句话说，我们希望找到1=i< i1 <.< ik-1 < ik =n+1来最小化(ai +.+ ai1-1)^2 + (ai1 +.+ ai2-1)^2 + (aik-1 +.+ aik-1)^2，使2 <= i1 -I <= 4，2 <= i2 - i1 <= 4，.，2 <= ik - ik-1 <= 4.提出了一种求解该问题的O(n)-time动态规划算法。
我的问题:定义子问题。我唯一的线索是不断地找到长度4到2的最小和，但是如果有1剩余的话呢？它是与现有的长度为2或3的组连接，还是与4组分离？更别说在O(N)里完成了.
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-12-15 07:07:16
子问题是:在第一个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的值，并将它们存储在一个数组中。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8516232
复制相关文章
相似问题
腾讯云开发者
