动态规划（五）

最小代价子母树-问题 问题描述：设有n堆沙子排成一排，其编号为1，2，3，…，n（n<=100）。每堆沙子有一定的数量，如下表： 13 7 8 16 21 4 18 现要将n堆沙子归并为一堆。归并的过程为每次只能将相邻的两堆沙子堆成一堆，这样经过n-1次归并之后最后成为一堆。如上面7堆沙子，可以有多种方法归并成一堆。其中的2种方法入下图： 16 21 4 18 13 7 8 20 24 25 44 69 87

最小代价子母树-问题 16 21 4 18 13 7 8 15 37 22 28 87 59 归并的代价是这样定义的，将两堆沙子归并为一堆时，两堆沙子数量的和称为归并2堆沙子的代价。如上图中，将7和8归并为一堆的代价为20。归并的总代价指的是将沙子全部归并为一堆沙子的代价的和。如上面的2种归并方法中， 第1种的总代价为 20+24+25+44+69+87 = 267 第2种的总代价为 15+37+22+28+59+87 = 248 由此可见，不同归并过程得到的总的归并代价是不一样的。 问题：当n堆沙子的数量给出后，找出一种合理的归并方法，使总的归并代价为最小。

最小代价子母树-分析 根据问题描述，深刻理解问题。画出一些简单的最小代价子母树。 （1）n=2 13 7 20 当n=2时，仅有一种堆法，因此总的归并代价为2堆沙子数量之和。

最小代价子母树-分析 （2）n=3 请你先画一画有几种堆法 总代价=15+28=43 总代价=20+28=48 13 7 8 15 28 13 7 8 20 28 总代价=15+28=43 总代价=20+28=48 当n=3时，有2种堆法。由于最后归并的代价为全部沙子数量的和，对任何归并方案都是相同，因此总的代价将取决于第一次归并。由于左边堆法第一次归并代价为15，优于右边堆法20，因此总代价左边为优。

最小代价子母树-分析 （3）n=4 请你先画一画有几种堆法。 13 7 8 15 28 16 44 13 7 8 20 28 16 44 24 (c) 总代价=20+24+44=88 (a) 总代价=20+28+44=92 (b) 总代价=15+28+44=87 16 13 7 8 24 44 31 16 13 7 8 15 44 31 (d) 总代价=15+31+44=90 (e) 总代价=24+31+44=99

最小代价子母树-分析 （3）n=4 时共有5种堆法。这5种堆法可以分成3类： 第1类：先归并1~3堆，再与第4堆归并。这是上图(a)、(b)的情形。可以看到(b)要占优是因为(b)中1~3堆是最小代价归并方案。 第2类：先归并1~2堆，3~4堆，再归并为一堆。这是上图(c)的情形。 第3类：先归并2~4堆，再与第1堆归并。这是上图(d) 、(e)的情形。可以看到(d)要占优是因为(d)中2~4堆是最小代价归并方案。 归纳上述分析，我们可以得出这样的结论： （1）如果把归并1~4堆看成整个问题，则这个问题可以分解为三个归并方案，每个归并方案包含1~2个子问题： ①　归并1~3；再与4归并 ②　归并1~2，归并3~4；再归并 ③　归并2~4；再与1归并 （2）问题的最优解必然是这三种分解方案之一的结果为最优。从上图可以看到，是①方案的结果为最优。而①方案实际有两种堆法，可以看到最终入选的是归并1~3的最优解。也就是说，在问题（归并1~4堆）的一个最优解中，包含着子问题（归并1~3堆）的一个最优解。

最小代价子母树-分析 （3）请一定要注意的是，参与“竞选”的②③两种方案的子问题也必须是由子问题的最优解构成，否则根本没有机会获胜。例如，在归并2~4堆的子问题中，只有(d)有机会获胜，调小第4堆的数值可以实现这一点，大家可以试一试。但是不管怎样调小数值，(e)都不可能获胜。因为(e)不是归并2~4堆的最优解，(d)才是！ 同样，在②方案中，归并1~2，归并3~4两个子问题也都是最优解。 （4）如果我们继续分析增加更多堆数进行归并的问题，就会发现n个沙堆归并时，会分解为n-1种类型： Case1: “归并”第1堆，归并2~n堆；再最后归并 Case2: 归并1~2堆，归并3~n堆；再最后归并 Case3: 归并1~3堆，归并4~n堆；再最后归并 …… Case n-2: 归并1~n-2堆，归并n-1~n堆；再最后归并 Case n-1: 归并1~n-1堆，“归并”第n堆；再最后归并

最小代价子母树-分析 在Case1和Case n-1两种情况中，都是一堆沙与另n-1堆沙归并。一堆沙没有归并代价，为了形式上的统一，我们把一堆沙的归并代价设为0。 这样，在所有n-1种情况中，都是先归并左右两个子问题，求出子问题的最小代价，再归并在一起。 致此，我们分析出了问题的最优子结构性质。

最小代价子母树-分析 递归地定义最优解的值 在前面的的分析中，我们看到问题的归并代价实际上由两部分组成： （1）归并树左右子树的最小代价之和 （2）归并树所有叶结点的权值之和 16 13 7 8 15 44 31 13 7 8 15 28 16 44 16 13 7 8 20 44 24 (c) 总代价=20+24+44=88 (d) 总代价=0+46+44=90 (b) 总代价=43+0+44=87

最小代价子母树-分析 递归地定义最优解的值 引入记号F(i,j)表示从第i堆沙到第j堆沙的归并最小代价。 F(1,1) =0 16 13 7 8 15 44 31 13 7 8 15 28 16 44 16 13 7 8 20 44 24 (d) 总代价=0+46+44=90 (b) 总代价=43+0+44=87 (c) 总代价=20+24+44=88

最小代价子母树-分析 递归地定义最优解的值 引入记号G(i,j)表示第i堆沙到第j堆沙的数量和。 G(1,1)=13 G(1,2)=20 16 13 7 8 15 44 31 13 7 8 15 28 16 44 16 13 7 8 20 44 24 (d) 总代价=0+46+44=90 (c) 总代价=20+24+44=88 (b) 总代价=43+0+44=87

最小代价子母树-分析 递归地定义最优解的值 因此，F(1,4) = MIN{F(1,1)+F(2,4), F(1,2)+F(3,4), F(1,3)+F(4,4)}+G(1,4) {归并1~4} F(2,4)=MIN{F(2,2)+F(3,4), F(2,3)+F(4,4)}+G(2,4) {归并2~4} F(3,4)=MIN{F(3,3)+F(4,4)}+G(3,4) {归并3~4} F(1,3)=? F(1,2)=? 我们看到归并1~4沙堆的子问题不只包括1~2, 1~3等，还包括2~3, 3~4, 2~4等。因此我们定义问题时不能只定义为F(n), 意思是合并1~n堆沙。而必须定义为F(i,j). 13 7 8 15 28 16 44 16 13 7 8 15 44 31 16 13 7 8 20 44 24 (c) 总代价=20+24+44=88 (b) 总代价=43+0+44=87 (d) 总代价=0+46+44=90

最小代价子母树-分析 递归地定义最优解的值 F(i,j)= MIN{F(i,i)+F(i+1,j), F(i,i+1)+F(i+2,j), …, F(i,j-2)+F(j-1,j), F(i,j-1)+F(j,j)}+G(i,j) 递归式的边界条件是: F(i,j) = 0 IF i=j 将两式合二为一，得到： 以上公式表明，在计算F(i,j)时，仅依赖于长度小于j-i+1的子问题F(i,k)和F(k+1,j)。这就为我们自底向上地计算F(i,j)创造了条件。

最小代价子母树-分析 自底向上地计算子母树的最小代价 下面我们从底向上地计算出n=4的子母树的最小代价。 G(i,j) F(i,j) 87 长度=4 44 31 28 43 46 长度=3 20 15 24 20 15 24 长度=2 16 13 7 8 长度=1 G(i,j) F(i,j)

最小代价子母树-分析 自底向上地计算子母树的最小代价 阶段 在向底向上地计算长度为n的沙堆时，可以分为1个初始阶段和n-1个计算阶段。 初始阶段做二件事： （1）将n堆沙的初值放入G表的最底层（G（i,i）的值，表示长度为1的沙堆的数值之和）； （2）将F表的最底层的n个位置清为0（F（i,i）的值，表示归并长度为1的沙堆的代价） n-1个计算阶段：由于是自底向上地计算，因此，归并的沙堆长度应该从2开始，逐步增加，3，4，…，n-1，直到长度为n，得到最后要求的结果F(1,n)。

最小代价子母树-分析 自底向上地计算子母树的最小代价 状态 在计算长度为2的阶段时，由于总的沙堆数为n，要分别计算出F(1,2), F(2,3), …,F(n-1,n)，共有n-1个状态。 在计算长度为3的阶段时，要分别计算F(1,3), F(2,4), …F(n-2,n)共有n-2个状态。 …… 在计算长度为n-1的阶段时，要分别计算F(1,n-1), F(2,n)共有2个状态。 在计算长度为n的阶段时，要计算F(1,n)共一个状态。

最小代价子母树-分析 自底向上地计算子母树的最小代价 决策 由于F(i,j)=Min{F(i,k)+F(k+1,j)}+G(i,j) i<=k<=j-1，因此k的取值范围是j-1-i+1=j-i 。 K值不同，将得到不同的F(i,k)+F(k+1,j)，其中最小的F(i,k)+F(k+1,j)才是所要的值。因此在计算F(i,j)时，必须要在这j-i 个k值带来F(i,k)+F(k+1,j)中作出决策。也就是说j-i 就是决策数。 在计算每个长度为2的F值时，要分别计算出F(1,2), F(2,3), …,F(n-1,n)，每个决策数为1。 在计算长度为3的阶段时，要分别计算F(1,3), F(2,4), …F(n-2,n)，每个决策数为2。 …… 在计算长度为n-1的阶段时，要分别计算F(1,n-1), F(2,n)，每个决策数为n-2。 在计算长度为n的阶段时，要计算F(1,n)，每个决策数为n-1。

最小代价子母树-分析 自底向上地计算子母树的最小代价 存储数据结构 由： F(1,1), F(2,2), … ,F(n-1, n-1), F(n,n) 长度为1 F(1,2), F(2,3), …,F(n-2,n-1),F(n-1,n) 长度为2 …… F(1,n-1), F(2,n) 长度为n-1 F(1,n) 长度为n 我们自然想到由一个n×n的二维数组的上三角部分来存储F表。 同理，由一个n×n的二维数组的上三角部分来存储G表。

最小代价子母树-分析 自底向上地计算子母树的最小代价 存储数据结构 F表 G表 16 13 7 8 20 15 24 28 31 44 20 20 15 24 43 46 87 F表

最小代价子母树-分析 自底向上地计算子母树的最小代价 程序 Procedure ZiMuShu; var i,j,k,m,L,t: integer; begin for i :=1 to n do begin {初始阶段} G[i,i] := H[i]; {H存储n个沙堆的数值} F[i,i] := 0; end; for m := n-1 downto 1 do {n-1个阶段} for i := 1 to m do begin {m个状态} L := n - m + 1; {归并的沙堆长度} j :=i + L - 1; {归并的沙堆的上限编号}

最小代价子母树-分析 自底向上地计算子母树的最小代价 程序 for k := i to j do {计算G[i,j]} G[i,j] := G[i,j] + G[k,k]; F[i,j] := MaxCost; {MaxCost表示正无穷大} for k := i to j-1 do begin {枚举j-i 个决策} t := F[i,k] + F[k+1,j] + G[i,j]; if t < F[i,j] then F[i,j] := t; {存储更小的代价} end; end; {ZiMuShu}

最小代价子母树-分析 自底向上地计算子母树的最小代价 主程序 program ZMS; const MaxN = 7; H : array[1..MaxN] of integer = (13, 7, 8 ,16, 21, 4, 18); MaxCost = MaxInt; var n : integer; F : array[1..MaxN, 1..MaxN] of integer; G : array[1..MaxN, 1..MaxN] of integer; Begin fillchar(F, sizeof(F), 0); fillchar(G, sizeof(G), 0); n := MaxN; ZiMuShu; {调用动态规划过程计算} writeln(F[1,n]); End.

最小代价子母树-分析 求出最优解的形成路径 经过前几讲动态规划的学习，我们知道需要有另外的存储结构来记录动态求解过程中得到的每个阶段的最优解的位置信息。 用W[1..MaxN, 1..MaxN]二维数组来记录每个阶段计算F[i,j]时，组成最优解的左、右沙堆分割位置k。 在前面的讨论中都知道： F[i,j] = min{F[i,k] + F[k+1,j]} + G[i,j] 也就是说，要得到最优的F[i,j]，应该先归并i~k堆沙，归并k+1~j堆沙，再将归并后形成的2堆沙归并为1堆，得到F[i,j]。 因此，W[i,j]记录了归并i~j堆沙的分割点。 在动态求解过程中，应该在得到更优的F[i,j]时，记录此时的分割点k。 F[i,j] := MaxCost; {MaxCost表示正无穷大} W[i,j] := 0; {分割位置初值为0，表示没有分割} for k := i to j-1 do begin {枚举j-i 个决策} t := F[i,k] + F[k+1,j] + G[i,j]; if t < F[i,j] then begin F[i,j] := t; {存储更小的代价} W[i,j] := k; end;

最小代价子母树-分析 求出最优解的形成路径 W[1,n]用来记录最后一次归并的左、右沙堆分割位置。将沙堆分割为1~W[1,n], W[1,n]+1~n。 先将1~W[1,n]归并为一堆，以及W[1,n]+1~n归并为一堆后再合二为一，最后成为一堆，完成归并1~n堆。 而沙堆1~W[1,n]的分割点位于W[1, W[1,n]]; 沙堆W[1,n]+1~n的分割点位于W[W[1,n]+1,n]; 这两个值是倒数第2层归并的分割点。 显然这是一个递归的过程，是一个对归并二叉树进行后序遍历的过程。我们用对左、右子树加括号的形式来表明沙堆归并的先后次序。 Procedure Print(i,j : integer); Var k:integer; Begin if i = j then write(H[i]:2) {I=j表明不能再进一步分割，到叶子结点了，输出} else begin k := W[i,j]; {找到I~j间的分割点} write(‘(’); {输出左子树的左半括号} Print(i,k); {输出左子树} write(‘)(’); {输出左子树的右半括号和右子树的左半括号} Print(k+1,j); {输出右子树} write(')'); end; End;

上机编程并调试本程序 完整录入源程序，只对13，7，8，16等四堆沙进行归并，单步调试，深刻理解动态规划执行过程中完成的各步骤的意义。 增加一堆沙，n=5时，再单步执行，看看n=4得到的结果（子问题的最优解）对n=5（问题）所进行的计算有什么直接贡献。 求出所有7堆沙的最优解和沙堆合并过程。 如果问题变为最大代价子母树，还满足用动态规划求解的要求吗？如果满足，试修改程序，求得最大代价子母树的最优解。 手工画出动态规划算法将5堆沙 6 12 5 8 9 归并为最小代价子母树的画形。

竞赛实题练习 石子合并（NOI95） 加分二叉树（NOIP03）

加分二叉树 【问题描述】 设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空 子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出； （1）tree的最高加分 （2）tree的前序遍历   【输入格式】 第1行：一个整数n（n＜30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。 【输出格式】 第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 3 1 2 4 5