這個題目來自TopCoder SRM 533 Div1 250分的題目 CasketOfStar。
原題
CasketOfStar
題意
有一個星星隊列科汗，每一個都有一個權(quán)重程奠，每次挑選一個（不能是收尾）侧戴，將它消滅，獲得的分?jǐn)?shù)為它相鄰的兩個的乘積瓷患。求最后最大的分?jǐn)?shù)值。
例如 {1,2,3,4}遣妥，先消滅3擅编，再消滅2，可以得到2 * 4 + 1 * 4 = 12 的分?jǐn)?shù)箫踩，如果先消滅2再消滅3只能得到13+14 = 7 分爱态。
思路
一開始看到這個題的時候覺得是貪心，后來找不到貪心方案境钟，只能往區(qū)間的方向去想锦担，我們用f[i][j]表示區(qū)間f[i][j]的最優(yōu)解，對于一個區(qū)間f[i][j],如果這個區(qū)間里面剩下3個元素慨削，無論中間的元素k是什么洞渔？最后一步增加的權(quán)重都是weight[i] * weight[j]，也就是最后的答案只跟f[i][k], f[k][j]的值有關(guān)缚态！
我們不難想到狀態(tài)轉(zhuǎn)移公式
f[i][j] = max{f[i][k] + f[k][j]} + weight[i] * weight[j];
這是一個明顯的區(qū)間動態(tài)規(guī)劃的問題磁椒。
核心代碼（JAVA）
for (int l = 3; l <= n; ++l){
for (int i = 0; i + l - 1 < n; ++i){
int j = i + l - 1;
for (int k = i + 1; k < j; ++k){
f[i][j] = Math.max(f[i][j], f[i][k] + f[k][j] + weight[i] * weight[j]);
}
}
}
