44-算法设计
4.8.2 算法设计
1．路边玩法
假设有n堆石子，一字排开，合并相邻两堆的石子，每合并两堆石子有一个花费，最终合并后的最小花费和最大花费。
（1）确定合适的数据结构
采用一维数组a[i]来记录第i堆石子（ai）的数量；sum[i]来记录前i堆（a1，a2，…，ai）石子的总数量；二维数组Min[i][j]、Max[i][j]来记录第i堆到第j堆ai，ai+1，…，ai堆石子合并的最小花费和最大花费。
（2）初始化
输入石子的堆数n，然后依次输入各堆石子的数量存储在a[i]中，令Min[i][i]=0，Max[i][i]=0，sum[0]=0，计算sum[i]，其中i= 1，2，3，…，n。
（3）循环阶段
- 按照递归式计算2堆石子合并{ai，ai+1}的最小花费和最大花费，i=1，2，3，…，n−1。
- 按照递归式计算3堆石子合并{ai，ai+1，ai+2}的最小花费和最大花费，i=1，2，3，…，n−2。
- 以此类推，直到求出所有堆{a1，…，an}的最小花费和最大花费。
（4）构造最优解
Min[1][n]和Max[1][n]是n堆石子合并的最小花费和最大花费。如果还想知道具体的合并顺序，需要在求解的过程中记录最优决策，然后逆向构造最优解，可以使用类似矩阵连乘的构造方法，用括号来表达合并的先后顺序。
2．操场玩法
圆型石子合并经常转化为直线型来求，也就是说，把圆形结构看成是长度为原规模两倍的直线结构来处理。如果操场玩法原问题规模为n，所以相当于有一排石子a1，a2，…，an，a1，a2，…，an−1，该问题规模为2n−1，然后就可以用线性的石子合并问题的方法求解，求最小花费和最大花费的方法是一样的。最后，从规模是n的最优值找出最小值即可。即要从规模为n的最优值Min[1][n]，Min[2][n+1]，Min[3][n+2]，…，Min[n][2n−1]中找最小值作为圆型石子合并的最小花费。
从 规模是 n 的最优值 Max[1][n]，Max[2][n+1]，Max[3][n+2]，…，Max[n][2n−1] 中找 最大值 作为圆型石子合并的最大花费。