每天一个TopCoder算法题（16.08.03）

这个题目来自TopCoder SRM 533 Div1 250分的题目 CasketOfStar。

原题

CasketOfStar

题意

有一个星星队列，每一个都有一个权重，每次挑选一个（不能是收尾），将它消灭，获得的分数为它相邻的两个的乘积。求最后最大的分数值。
例如 {1,2,3,4}，先消灭3，再消灭2，可以得到2 * 4 + 1 * 4 = 12 的分数，如果先消灭2再消灭3只能得到13+14 = 7 分。

思路

一开始看到这个题的时候觉得是贪心，后来找不到贪心方案，只能往区间的方向去想，我们用f[i][j]表示区间f[i][j]的最优解，对于一个区间f[i][j],如果这个区间里面剩下3个元素，无论中间的元素k是什么？最后一步增加的权重都是weight[i] * weight[j]，也就是最后的答案只跟f[i][k], f[k][j]的值有关！
我们不难想到状态转移公式

f[i][j] = max{f[i][k] + f[k][j]} + weight[i] * weight[j];

这是一个明显的区间动态规划的问题。

核心代码（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]);
            }
        }
    }