石子合并问题
石子合并问题
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n 堆石子合并成一堆的最小得分和最大得分。 分析：
假设有n 堆石子需要合并, 可以设计一个2*n-1个元素的数组来存储每堆石子的个数。
分析最优解的结构：假设有石头AiAi+1……Aj 需要合并, 简记为A[i,j].如果设最后一次合并发生在Ak 与Ak+1之间(i
置,totalValue(i,j)的值都是一样的) 因此总的得分等于A[i,k]的得分加上A[k+1,j]的得分再加上totalValue(i,j).
可以假设计算A[0,n-1]的一个最优次序所包含的计算子链A[0,k]和A[K+1,n-1]的次序也是最优的.
证明:
假设存在一个比计算A[0,k]的次序得分更少的次序, 则用此次序来替换原来计算A[0,k]的次序, 那么此时计算A[0,n-1]次序的得分就会比最优次序所得到的分数更少, 这与假设相矛盾; 同理可证明:计算A[0,n-1]的一个最优次序所包含的另一个计算子链A[k+1,n-1]的次序也是最优的!
综上所述, 此题满足最优子结构性质, 因此可以用动态规划算法来求解.
建立递归关系
设m[i][j]表示A[i,j]的计算结果.
当i=j时, 表示只有一堆石头, 不能合并, 因此得分为零, 所以m[i,j]=0;
当i
m[i,j]=m[i,k]+m[k+1,j]+totalValue(i,j)(i
可用矩阵连乘的最优计算次序问题来求解这题. 可选用自顶向下的备忘录算法或是自底向上的动态规划算法.
以下代码使用动态规划算法:
[cpp] view plaincopy
1. void MatrixChain(int *p,int n,int **m,int flag) //矩阵连乘算法
2. {
3. for (int i=0;i
4. m[i][i]=0;
5. for (int r=2;r
6. for (int i=0;i
7. {
8. int j=i+r-1;
9. int temp=totalValue(i,j,p);
10. m[i][j]=m[i+1][j]+temp;
11. for (int k=i+1;k
12. {
13. int t=m[i][k]+m[k+1][j]+temp;
14. if (!flag) //求最小得分
15. {
16. if (t
17. m[i][j]=t;
18. }
19. else //求最大得分
20. if (t>m[i][j])
21. m[i][j]=t;
22. }
23. }
24. }
25. MatrixChain(inputNum,2*n-1,m,0); //计算最小得分
26. int resultMin=m[0][n-1];
27. for (i=1;i
28. if (resultMin>m[i][n-1+i])
29. resultMin=m[i][n-1+i];
30.
31. MatrixChain(inputNum,2*n-1,m,1); //计算最大得分
32. int resultMax=m[0][n-1];
33. for (i=1;i
34. if (resultMax
35. resultMax=m[i][n-1+i];