Description

在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新一堆石子数记为该次合并的得分。试设计一个动态规划算法，计算出将n堆石子合并成一堆的最小得分和最大得分，要求列出递归方程，写出算法的伪代码并分析算法的时间空间复杂性。

分析

要求每次合并必须是相邻的，和矩阵链乘的括号作用差不多。可以考虑往矩阵链乘最小代价的递归方程上靠。设dp[i,j]为第i堆到第j堆合并的最优解，则\(dp[i,j] = min\{dp[i,k]+dp[k+1,j]+v_i+...v_j\}\)

注意由于是圆形，而矩阵链乘是线性的，所以这个递归方程势必需要修改。考虑如何表示环，一个自然的想法是利用mod函数。递归方程修改如下，为了方便表示修改dp[i,j]定义如下：从第i堆开始合并j堆的最优解。（否则需要填写的项数不全在一个矩阵半角上）

\(dp[i,j] = min\{dp[i,k]+dp[(i+k)\%n, j-k]+v_i+...+v_j\}~~~~ i<=k<=j\)

\(dp[i,j] = max\{dp[i,k]+dp[(i+k)\%n, j-k]+v_i+...+v_j\}~~~~ i<=k<=j\)

一点思考

总觉得和之前那道折木棒的很像，画个解的树表示看看，发现几乎一致，同样是求树的所有内部节点的值的和。但是不同的是，对叶节点有限制，即从左到右需要严格按照\(v_1, v_2, ..., v_n\) 排列。那么同样可以利用哈夫曼树的思想解决。维护一个叶节点的数组，每次选择相邻中最小最大的一组\((v_i, v_j)\)，生成一个子树，同时将\(v_i,v_j\)删去，新的叶节点\(v_i+v_j\)放入原来\(v_i\)位置。同样可解问题。

直觉两者应该是一个系列的题，去Bing一下。果不其然：