比较容易想到的解法就是区间型的DP。令状态dp[i][j]表示将[i,j]之间的元素最终聚成一个元素所需要的cost。显然，突破点就是如何将这个区间划分为左右两个分支，这就需要遍历可能的内部分界点k。这样的话，就可以得到状态转移方程：
dp[i][j] = min(dp[i][k]+dp[k+1][j]+largest[i][k]*largest[k+1][j])
需要注意，largest[k+1][j]需要提前处理，这可能需要设计另外一个dp过程：
largest[i][j] = max(largest[i][i],largest[i+1][j])
这样的解法时间复杂度是o(N^3).
更优秀的解法需要对于题意做进一步的理解。
我们可以想象，每一次对两个节点做“归并”，就是消灭较小的数，保留较大的数。所以整个过程可以理解为：对于arr的数组，每次取当前相邻的两个元素进行归并，较小的元素被消失，较大的元素保留，其cost是两者的乘积。注意，消失的元素会使得原先不相邻的两个元素变得相邻。问经过N-1次归并之后的最小cost总和是多少。
所以对于任何一个元素，它只能是在与更大的元素相遇之后才能被消失，否则会一直存在。那么更大的元素是什么呢？就两种选择：左边第一个比它大的数，右边第一个比它大的数。显然，为了减小cost，我们必然选择让它和较小的那个候选数去碰撞。体会一下，对于每个元素，它所作的选择都是独立的，不会相互冲突。举个例子：ABCDEF，对于D而言，如果我们可以判定它和A碰撞最优（当然A>D)，那么对于B或者C的碰撞对象的选择没有任何影响。这是因为允许D选择A的隐含信息就是BC都比A小，B和C必定只能限制在A和D之间选择。
所以算法的大致思想就是：对于每个元素arr[i]，我们考察它被消去时候的cost，然后总cost相加就是答案。（显然，我们只有N-1次相消，因为最大的元素是不可能被消去的）。单个元素的cost，就是在其左边第一个比它大的数a，右边第一个比它大的数b，两者之间选择，即 arr[i]*min(a,b)。求一个数组里每一个元素的左边（或者右边）第一个比它大的元素，就是典型的单调栈的应用。参考496.next greater element.
有两个细节需要注意。
首先，如果一个元素的左边没有比它更大的数，但它仍有可能被（右边更大的数）消去，那么我们就定义a=INT_MAX.对于右边的情况同样处理。
其次，以上的算法中严格要求了所有的元素都能比较（分出大小）。如果两个元素的数值相等，我们必须额外定义一个区分大小的原则。最简单的方法就是，数值相等的元素，右边的更大。如果我们不这样处理，会遇到这样的情况：xxxx A1 A2 xxx，当A1与A2相等时，如果我们考虑A1可以被A2消去，且考虑A2可以被A1消去，那么会有两次cost的相加。但事实上A1与A2的碰撞只应该计算一次cost。