此题很难。本质上这题用了DP的状态转移的思想，但是bottom-up却并不好写，实际上用的是DFS＋记忆化的方法。当然，依然用到了状态数组，所以仍然可以看做一道DP题。
此题第一眼看上去，很容易让人想尝试区间型DP的解法。毕竟有其他很多题都是类似的意境：比如312.Burst-Balloons，1000.Minimum-Cost-to-Merge-Stones等等。那我们先来尝试一下。
我们考虑dp[l][r]表示在区间[l,r]内我们消灭所有盒子的最优值。区间型dp的目标是将大区间化成小区间，一个常见的突破口就是从最后一个元素入手，看它能够怎么处理掉。假设我们看到的这个区间长这个样子：
... OOO XXX OOO XXX OOO
... ^ ^ ^ ^ ^
... j1 i1 j0 i0 r
最后一组OOO表示有若干个（可能只有一个）相同的元素（即boxes[r]）。同时在这个区间里有若干个subarray也有可能与boxes[r]相同，我们也用OOO标记出来。其他任何不包含boxes[r]的subarray都用XXX标记。
最后一组OOO最粗暴的处理方法就是自己单独消去，那么至少有一个解就出来了：dp[l][i0] + count*count，其中count就是最后一组OOO的元素个数。
当然，我们还会有其他的处理方式。比如说：先处理i0这组XXX，然后我们发现r这组OOO和j0这组OOO就可以接在了一起。那么这意味着这种方法做下去的最优解就是dp[l][i1]+(count0+count)*(count0+count)+dp[j0+1][i0]了吗？并不是，因为j0这组OOO虽然带上了r这组OOO，但并不意味着最优解一定是将count0+count这部分消去；有可能j0这组OOO（带着r这组OOO）附着于j1这组OOO一起消去是更优的。具体哪种做法更优，取决于的竟然是count的数目！
举个例子：
XX O XX O ** O
^ ^ ^ ^
j1 i0 j0 r
我们已经决定将j0和r这组O放在一起。在这个例子里，最优的决策是：先消灭j1，然后将4个X消灭，再消灭j0+r的这两个O. 最后的得分是1+16+4=21。
再看另一个例子，唯一的区别就是r所属的O现在有3个。
XX O XX O ** OOO
^ ^ ^ ^
j1 i0 j0 r
在这个例子里，最优的决策是：先消灭i0，然后将j1+j0+r这五个O消灭，最后再消灭最前的XX，总得分是4+25+4=32.
所以结论是，当我们决定将r这组OOO跟着j0这组OOO的时候，对于[l,j0]这组区间的最优操作，需要参考r这组OOO的具体数目（也就是count）。因此常规的区间型DP的两个下标并不够，而需要第三个下标：dp[l][r][k]表示，对于区间[l,r]后面还跟着k个与boxes[r]相同的元素。注意这k个元素并不与r直接相连，而是经过其他之前的区间消除后剩下来的。
于是本题的状态转移就是，考虑r这组OOO与它之间的哪组OOO相连。在这个例子里，r可以与j0相连，于是dp[l][r][0]转化为dp[l][j0][count] + dp[j0+1][i0][0]。也可以跳过j0这组OOO，与j1相连，于是于是dp[l][r][0]转化为dp[l][j1][count] + dp[j1+1][i0][0]。依次类推，取最大值。
最后的结果是输出dp[0][N-1][0]
注意，因为我们事前并无法确认第三个下标k对于哪些[l,r]是有意义的，所以dp比较难写。因此这题用top-down的记忆化搜索更方便些。