石头合并问题的动规讨论.ppt

动态规划设计: 阶段i：石子的每一次合并过程，先两两合并，再三三合并，...最后N 堆合并 状态s：每一阶段中各个不同合并方法的石子合并总得分。 决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案 以 dp[i][j] 来表示 从i开始合并j个元素，dp[i，j] 表示 dp[i][j] 的最优解。 举例：9，7，6，9，20 dp[1][1] 表示 第一个元素和它自己合并 dp[1,1] = 0 dp[1][2] 表示 第一个元素 和他后面的一个元素合并 即 9,7合并 dp[1,2] = 16 dp[1,1] 到 dp[5,5] 的取值如下： 我们需要的是dp[1,5]，dp[i][5]，dp[5,5]的最小值。 可以得到最优解113 代码 运行结果： 谢谢 石头合并问题的动规讨论 内容描述： 在一个圆形操场的四周摆放着n 堆石子。现 将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。（因为最大与最小的寻找方式相同，在此只讨论寻找最小得分） 解决方案： 贪心算法： 以数据 9 6 7 9 20 为例 贪心的合并过程： 1、9 13 9 20 //6与7合并 score = 13 2、22 9 20 //9与13合并 score =22 3、22 29 //9与20合并 score = 29 4、51 //24，29合并 score = 51 总分： 13+22+29+51 = 115 动规合并过程：序列： 9 6 7 9 20 1、15 7 9 20 //9,6合并 score = 15 2、15 16 20 //7,9合并 score = 16 3、31 20 //15，16合并 score = 31 4、51 //31，20合并 score =50 得分 15+16+31+51= 113 分析： 因为贪心算法是一只寻找局部最优解，不能保证全局最优解，因此贪心算法不可取 动规讨论 ? 最优解结构的探讨：假设有 i,i+1,i+2,i+3,i+4,…,i+j 个石头堆合并。 则有合并方式 [ (i) (i+1,i+2,i+3,...,i+j) ] [ (i,i+1) (i+2,i+3,...i+j) ] [ (i,i+1,i+2) (i+3,...i+j) ] . . . [ (i,i+1,...,i+j-1) (i+j) ] 以G[i,j]表示从i 合并到j的得分， 则 G[i,j] == G[i,k]+G[k+1][j] + total(i,j) 其中total(i,j)为最后一次合并的得分 为石子的总数 而 G[i,k] , G[k+1][j]的总得分 ，也用上式求出