原题
题意
消除游戏大家都非常喜欢玩，今天我们来介绍一款消除游戏。有一个星星队列，每一颗星星上面都有一个分数，我们每次可以挑选一个进行消灭，每次消灭的得分等于相邻两个星星的分数乘积，举个例子，星星队列为｛2，4，6｝，那么消灭4，分数为2*6等于12。很显然，我们不能挑选队首跟队尾，一个长度为N的队列，经过N-2轮后游戏结束，求游戏结束时的最大分。
样例
41 2 3 4总共有4个星星，先消灭3，得到24=8分，剩下{1,2,4}，再消灭2，得到14=4分，总共12分。如果我们先消灭2，再消灭3，那么只能得到13+14=7分
思路
我们尝试找到消灭的规律，比如说先消灭大的，再消灭小的，也就是贪心算法。先找到一个贪心策略，然后再执行。可是我们很快就发现，先消灭大的，再消灭小的是错的。举个样例{4 2 3 4}，如果我们先消灭3，再消灭2只能得到24分，反之能得到28分！首先是重叠子问题，在一个序列当中，总是有区间包含的情况发生，比如有两个区间[1,10],[2,9],在求1到10的最优解的时候，就可能计算到2到9的最优解。其次是最优子结构我们当然希望每个区间的分数都最大，最后是无后性，我们从小区间开始算，最后才算大区间，大区间不会影响小区间。既然这个问题满足动态规划的3大前提，那么我们是否可以尝试下使用动态规划算法来进行解答。首先是划分状态，既然是一个序列，那么我们就可以一个区间一个区间进行划分。状态表示，我们用f[i][j]表示区间[i,j]的最大的分数。状态转移，对于一个[i,j]的区间，无论挑选那个元素，新增的得分都是weight[i]weight[j]，很明显，与原来的f[i][k]与f[k][j]息息相关， f[i][j] = max{f[i][k] + f[k][j]} + weight[i] * weight[j];确定边界*，最后的结果就是f[i][j]整个区间的长度，最小的区间长度是3。如果区间长度小于3，那么f[i][j]为0。最终算法复杂度为O(N^3)
总结
无论是谷歌Facebook,还是国内的BAT，动态规划问题在算法面试中占了举足轻重的作用。虽然动态规划算法看起来很难，但是只要掌握了一定的套路，再难的问题也可以迎刃而解。
