動態規劃最小化平方和

Question

我有一個練習考試這個問題，並不知道如何解決它，所以我非常害怕最後的決定。不管怎麼說，發現這個問題有答案會減輕，並會幫助我瞭解動態規劃，所以感謝您的閱讀:)

問題：

給定n數A的序列，...，的（正或負），我們 希望將序列劃分成塊，以便最小化的 的塊總和的平方，但須使每個 塊包含至少2個和最多4個元素的約束的總和。換句話說，我們 想要找到1 = [0] <我[1] <我[2] < ... <我[k-1] <我[k] = n + 1到 最小化（ai [ai [1] -1）^ 2 +（ai [1] + ... + ai [2] -1）^ 2 + ... + （ai [k-1] + ... + ai [k] -1）^ 2，從而使得[0121]= 4，[0] < = 4，2 < = [2] ...，2 < = I [K] - I [K-1] = < 4.（請注意，塊的數目k 未給出）。呈現O（N）-time動態編程 算法來解決問題。

我的問題：定義子問題。我唯一的線索是不斷地找到長度從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值和。