递归、分治、动态规划实例

1、递归、分治、动态规划与回溯 回溯 递归 递推一般实现方式正反方向有时可相互转化较简洁,要求数学规律性较强DFS穷举的优化版启发式搜索路径寻找图论/网络流数学问题：组合数学树、图、排序等问题分治、以大化小动态规划的实现DP=递归贪心回溯、递归、递推是计算机算法中基础内容，范围极其广泛。递归与分治基本原理n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。T(n/2)nT(n/2)T(n/2)T(n/2)T(n)=T(n/2)nT(n/2)T(n/2)T(n/2)T(n)=n对这k个子问题分别求解。如果子问题的规模

2、仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。递归与分治基本原理n/2T(n/4)T(n/4)T(n/4)T(n/4)n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T

3、(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)递归与分治基本原理递归、递推、分治 递归与递推表面看来是相逆的过程，其实也是相似的，最终的计算都是从小算到大。 递推的使用环境要求高导致了递推的高效性，递推没有重复计算什么数据，保持了高效。 递归大多数会重复计算子问题，导致时间浪费，所以一般不要使用过深的递归，甚至会空间溢出。 但是也不能说递推好，递归差，因为递归却能解决很多递推做不到的事情，在某些特定的环境下也能实现高效，并且递归容易使用。我们要就事论事！斐波那契数列（Fibonacci），对于f（3

4、0），如果使用递归则需要运行1664079次，而递推只需30次就可以了，速度悬殊。递归：long f (long n) if i1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。 例例5 5 整数划分问题整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1

5、+1。(2) q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即nn111 (4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1 的划分组成。(3) q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划

6、分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。 22/38二叉树二叉树1、问题描

7、述、问题描述图图1 满二叉树满二叉树 23/38问题描述问题描述 如上图所示，由正整数如上图所示，由正整数1, 2, 3, .组成了一棵无限大的二叉组成了一棵无限大的二叉树。从某一个结点到根结点（编号是树。从某一个结点到根结点（编号是1的结点）都有一条唯一的结点）都有一条唯一的路径，比如从的路径，比如从10到根结点的路径是到根结点的路径是(10, 5, 2, 1)，从，从4到根到根结点的路径是结点的路径是(4, 2, 1)，从根结点，从根结点1到根结点的路径上只包含到根结点的路径上只包含一个结点一个结点1，因此路径就是，因此路径就是(1)。 对于两个结点对于两个结点x和和y，假设他们到根结点的

8、路径分别是，假设他们到根结点的路径分别是(x1, x2, . ,1)和和(y1, y2, . ,1)（这里显然有（这里显然有x = x1，y = y1），），那么必然存在两个正整数那么必然存在两个正整数i和和j，使得从，使得从xi 和和 yj开始，有开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,. 现在的问题就是，给定现在的问题就是，给定x和和y，要求要求xi（也就是（也就是yj）。）。24/38问题描述问题描述输入格式输入格式输入只有一行，包括两个正整数输入只有一行，包括两个正整数x 和和y，这两个正，这两个正整数都不大于整数都不大于1000。

9、输出要求输出要求输出只有一个正整数输出只有一个正整数xi。输入样例输入样例10 4输出样例输出样例225/38n这个题目要求树上任意两个节点的最近公共子节点。分析这这个题目要求树上任意两个节点的最近公共子节点。分析这棵树的结构不难看出，不论奇数偶数，每个数对棵树的结构不难看出，不论奇数偶数，每个数对2 做整数除法，做整数除法，就走到它的上层结点。就走到它的上层结点。n我们可以每次让较大的一个数（也就是在树上位于较低层次我们可以每次让较大的一个数（也就是在树上位于较低层次的节点）向上走一个结点，直到两个结点相遇。的节点）向上走一个结点，直到两个结点相遇。n如果两个节点位于同一层，并且它们不相等，

10、可以让其中任如果两个节点位于同一层，并且它们不相等，可以让其中任何一个先往上走，然后另一个再往上走，直到它们相遇。何一个先往上走，然后另一个再往上走，直到它们相遇。n设设common(x, y)表示整数表示整数x 和和y的最近公共子节点，那么，的最近公共子节点，那么，根据比较根据比较x 和和y 的值，我们得到三种情况：的值，我们得到三种情况：n(1) x 与与y 相等，则相等，则common(x, y)等于等于x 并且等于并且等于y；n(2) x 大于大于y，则，则common(x, y)等于等于common(x/2, y)；n(3) x 小于小于y，则，则common(x, y)等于等于co

11、mmon(x y/2)；2、解题思路、解题思路26/383、参考程序、参考程序n#include nint common(int x, int y)nn if(x = y)n return x;n if(x y)n return common(x / 2, y);n returnn common(x, y / 2);nnint main(void)nn int m, n;n scanf(%d%d, &m, &n);n printf(%dn, common(m, n);n return 0;n27/38波兰表达式波兰表达式1、问题描述、问题描述 波兰表达式是一种把运算符前置的算术

12、表达式，例波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式如普通的表达式2 + 3 的波兰表示法为的波兰表示法为+ 2 3。波。波兰表达式的优点是运算符之间不必有优先级关系，兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如也不必用括号改变运算次序，例如(2 + 3) * 4 的的波兰表示法为波兰表示法为* + 2 3 4。本题求解波兰表达式的。本题求解波兰表达式的值，其中运算符包括值，其中运算符包括 + - * / 四个。四个。28/38问题描述问题描述n 输入数据输入数据 输入为一行，其中运算符和运算数之间都用空格分输入为一行，其中运算符和运算数之间都用空

13、格分隔，运算数是浮点数隔，运算数是浮点数n 输出要求输出要求 输出为一行，表达式的值。输出为一行，表达式的值。n 输入样例输入样例 * + 11.0 12.0 + 24.0 35.0n 输出样例输出样例 1357.00000029/38n这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太容易想清楚，但是如果用递归的思想就非常容易想清楚。让我容易想清楚，但是如果用递归的思想就非常容易想清楚。让我们根据逆波兰表达式的定义进行递归求解。在递归函数中，针们根据逆波兰表达式的定义进行递归求解。在递归函数中，针对当前的输入，有五种情况：对当前的输入

14、，有五种情况：n(1) 输入是常数，则表达式的值就是这个常数；输入是常数，则表达式的值就是这个常数；n(2) 输入是输入是+，则表达式的值是再继续读入两个表达式并计，则表达式的值是再继续读入两个表达式并计算出它们的值，然后将它们的值相加；算出它们的值，然后将它们的值相加；n(3) 输入是输入是-；n(4) 输入是输入是*； n(5) 输入是输入是/；n后几种情况与后几种情况与2）相同，只是计算从）相同，只是计算从+变成变成-，*，/。2、解题思路、解题思路30/383、参考程序、参考程序n#include n#includendouble exp(void)nn char a10;n scan

15、f(%s, a);n switch(a0)n n case+: return exp( ) + exp( );n case-: return exp( ) - exp( );n case*: return exp( ) * exp( );n case/: return exp( ) / exp( );n default: return atof(a);n n31/38nint main(void)nn double ans;n ans = exp();n printf(%f, ans);n return 0;n32/38放苹果放苹果1、问题描述、问题描述 把把 M 个同样的苹果放在个同样的苹果

16、放在N 个同样的盘子个同样的盘子里，允许有的盘子空着不放，问共有多少种里，允许有的盘子空着不放，问共有多少种不同的分法？（用不同的分法？（用K 表示）注意：表示）注意：5，1，1 和和1，5，1 是同一种分法。是同一种分法。 33/38问题描述问题描述n输入数据输入数据n第一行是测试数据的数目第一行是测试数据的数目t（0 = t = 20）。以下每）。以下每行均包含两个整数行均包含两个整数M 和和N，以空格分开。，以空格分开。1=M，Nm，必定有，必定有n-m 个盘子永远空着，去掉它们对摆放苹果方法个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即数目不产生影响；即if(nm) f(m,

17、n) =f(m,m)。当。当n m) nreturn f (m, m);nreturnf (m , n-1)+f (m-n , n);nn由上可知：当由上可知：当n=时，所有苹果都必须放在一个盘子里，所以返回时，所有苹果都必须放在一个盘子里，所以返回；当没有苹果可放时，定义为种放法；递归的两条路，第一条；当没有苹果可放时，定义为种放法；递归的两条路，第一条n 会逐渐减少，终会到达出口会逐渐减少，终会到达出口n=1; 第二条第二条m 会逐渐减少，因为会逐渐减少，因为nm 时，我们会时，我们会return f(m , m) 所以终会到达出口所以终会到达出口m=0n注：苹果注：苹果(相同或不同相同或

18、不同)放入盘子放入盘子(相同或不同相同或不同)的问题，在的问题，在组合数组合数学学中有更多的论述，可参考卢开澄的中有更多的论述，可参考卢开澄的组合数学组合数学(第第2版版)第第2章章中的中的Stirling数。数。36/383、参考程序、参考程序n#include nint count(int x, int y)nn if(y = 1 | x = 0) n return 1;n if(x y)n return count(x, x);n return count(x, y - 1) + count(x - y, y);n37/38参考程序参考程序nint main(void)nn int t,

19、 m, n;n scanf(%d, &t);n for(int i = 0; i t; i+)n n scanf(%d%d, &m, &n);n printf(%dn, count(m, n);n n return 0;n38/38红与黑红与黑1、问题描述、问题描述 有一间长方形的房子，地上铺了红色、黑色两有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。计算你总共能够到

20、达多少块黑色的瓷砖。39/38问题描述问题描述n输入数据输入数据n包括多个数据集合。每个数据集合的第一行是两个整数包括多个数据集合。每个数据集合的第一行是两个整数W 和和H，分别表示，分别表示x 方向和方向和y 方向瓷砖的数量。方向瓷砖的数量。W 和和H 都不超过都不超过20。在接下来的。在接下来的H 行中，每行包括行中，每行包括W 个字符。个字符。每个字符表示一块瓷砖的颜色，规则如下每个字符表示一块瓷砖的颜色，规则如下n(1).：黑色的瓷砖；：黑色的瓷砖；n(2)#：红色的瓷砖；：红色的瓷砖；n(3)：黑色的瓷砖，并且你站在这块瓷砖上。该字符：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数

21、据集合中唯一出现一次。在每个数据集合中唯一出现一次。n当在一行中读入的是两个零时，表示输入结束。当在一行中读入的是两个零时，表示输入结束。40/38问题描述问题描述n输出要求输出要求n对每个数据集合，分别输出一行，显示你从初始位对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数置出发能到达的瓷砖数(记数时包括初始位置的瓷砖记数时包括初始位置的瓷砖)。 输入样例输入样例输出样例输出样例6 9.#.#.#.#.#.#.0 04541/38n这个题目可以描述成给定一点，计算它所在的连通区域的面积。这个题目可以描述成给定一点，计算它所在的连通区域的面积。需要考虑的问题包括矩阵的大小，以及

22、从某一点出发向上下左需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左右行走时，可能遇到的三种情况：出了矩阵边界、遇到右行走时，可能遇到的三种情况：出了矩阵边界、遇到.、遇、遇到到#。n设设f(x, y)为从点为从点(x,y)出发能够走过的黑瓷砖总数，则出发能够走过的黑瓷砖总数，则n f(x, y) = 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1)n这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。每走过一块

23、瓷砖就将它作标记的方法保证不重复计算任何瓷砖。2、解题思路、解题思路42/383、参考程序、参考程序n#include nint W, H;nchar z2121;nint f(int x, int y)nn if(x = W | y = H) / 如果走出矩阵范围如果走出矩阵范围n return 0;n if(zxy = #)n return 0;n elsen n zxy = #; / 将走过的瓷砖做标记将走过的瓷砖做标记n return 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1);n n43/38参考程序参考程序ni

24、nt main(void)nn int i, j, num;n while(scanf(%d %d, &H, &W) & W != 0 & H != 0)n n num = 0;n for(i = 0; i W; i+) / 读入矩阵读入矩阵n scanf(%s, zi);n for(i = 0; i W; i+)n for(j = 0; j H; j+)n if(zij = ) printf(%dn, f (i , j);n n return 0;ndivide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的

25、问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡平衡(balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要好。一个分治法将规模为n的问题分成k个规模为n

26、m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：11)()/() 1 ()(nnnfmnkTOnT通过迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT注意注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n

27、)T(mi+1)。 分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。 分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现

28、要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：public static int

29、binarySearch(int a, int x, int n) / 在 a0 = a1 = . = an-1 中搜索 x / 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法复杂度分析：算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个

30、算法在最坏情况下的计算时间复杂性为O(logn) 。 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法: abcd复杂度分析复杂度分析T(n)=O(n2) 没有改进没有改进11)()2/(4) 1 ()(nnnOnTOnTX = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2)

31、效率太低u分治法: XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度，必须减少乘法的次数。XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd1.XY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd复杂度分析复杂度分析T(n)=O(nlog3) =O(n1.59) 较大的改进较大的改进11)()2/(3) 1 ()(nnnOnTOnT细节问题细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。 请设计一个有效的算法，可以进行两个

32、请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法: O(n1.59) 较大的改进u更快的方法?如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。A和B的乘积矩阵C中的元素Ci,j定义为: nkjkBkiAjiC1若依此定义来计算A和B的乘积矩阵C，则每计算C的一

33、个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(n3)u传统方法：O(n3)使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:222112112221121122211211BBBBAAAACCCC由此可得：2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC复杂度分析复杂度分析T(n)=O(n3) 没有改进没有改进22)()2/(8) 1 ()(2nnnOnTOnTu传统方法：O(n3)u分治法:

34、为了降低时间复杂度，必须减少乘法的次数。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC复杂度分析复杂度分析T(n)=O(nlog7) =O(n2.81) 较大的改进较大的改进22)()2/(7) 1 ()(2nnnOnTOnTu传统方法：O(n3)u分治法: O(n2.81)u更快的方法?Hopcro

35、ft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。private static int partition (int p, int r) int i = p, j = r + 1; Comparable x = ap; / 将= x的元素交换到左边区域 / 将= x的元素交换到右边区域 while

36、 (true) while (a+pareTo(x) 0); if (i = j) break; MyMath.swap(a, i, j); ap = aj; aj = x; return j; 初始序列6, 7, 5, 2, 5, 8j-;ji5, 7, 5, 2, 6, 8i+;ji5, 6, 5, 2, 7, 8j-;ji5, 2, 5, 6, 7, 8i+;ji完成快速排序具有不稳定性不稳定性。6, 7, 5, 2, 5, 85, 2, 5 6 7, 8private static int randomizedPartition (int p, int r) int i = rando

37、m(p,r); MyMath.swap(a, i, p); return partition (p, r); 快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)&稳定性：不稳定稳定性：不稳定设计一个满足以下要

38、求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。1234567821436587341278564321876556781234658721437856341287654321设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-

39、1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。1234567821436587341278564321876556781234658721437856341287654321n找出最优解的性质，并刻划其结构特征。n递归地定义最优值。n以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这最优解包含着其子问题的最优解。这种性质称为种性质称为最优子结构性

40、质最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后

41、将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。 2021-12-2962动态规划例题动态规划例题( (I) )数字三角形 1、问题描述、问题描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳一个和，和最大的路径称为最佳路径。你的任

42、务就是求出最佳路径上的数字之和。路径上的数字之和。注意：路径上的每一步只能从一个数走到下一层上和它最近的注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。左边的数或者右边的数。问题描述输入数据输入数据输入的第一行是一个整数输入的第一行是一个整数N (1 N = 100)，给出，给出三角形的行数。下面的三角形的行数。下面的N 行给出数字三角形。数字三行给出数字三角形。数字三角形上的数的范围都在角形上的数的范围都在0 和和100 之间。之间。输出要求输出要求输出最大的和。输出最大的和。问题描述输入样例输入样例573 88 1 02 7 4 44 5 2 6 5输出样例输出

43、样例302、解题思路 这道题目可以用递归的方法解决。基本思路是：这道题目可以用递归的方法解决。基本思路是：以以D( r, j)表示第表示第r 行第行第 j 个数字个数字(r，j 都从都从1 开始算开始算)，以，以MaxSum(r, j) 代表从第代表从第 r 行的第行的第 j 个数字到底边的最佳路径个数字到底边的最佳路径的数字之和，则本题是要求的数字之和，则本题是要求 MaxSum(1, 1) 。从某个从某个D(r, j)出发，显然下一步只能走出发，显然下一步只能走D(r+1, j)或者或者D(r+1, j+1)。如果走。如果走D(r+1, j)，那么得到的，那么得到的MaxSum(r, j)

44、就是就是MaxSum(r+1, j) + D(r, j)；如果走；如果走D(r+1, j+1)，那么得，那么得到的到的MaxSum(r, j)就是就是MaxSum(r+1, j+1) + D(r, j)。所。所以，选择往哪里走，就看以，选择往哪里走，就看MaxSum(r+1, j)和和MaxSum(r+1, j+1)哪个更大了。哪个更大了。3、参考程序 I#include #define MAX_NUM 100int DMAX_NUM + 10MAX_NUM + 10;int N;int MaxSum( int r, int j)if( r = N )return Drj;int nSum1

45、= MaxSum(r+1, j);int nSum2 = MaxSum(r+1, j+1);if( nSum1 nSum2 )return nSum1+Drj;return nSum2+Drj; 3、参考程序 Iint main(void)int m;scanf(%d, &N);for( int i = 1; i = N; i + )for( int j = 1; j = i; j + )scanf(%d, &Dij);printf(%d, MaxSum(1, 1);return 0;提交结果：提交结果：Time Limit Exceed程序I分析 上面的程序，效率非常低，在上

46、面的程序，效率非常低，在N 值并不大，值并不大，比如比如N=100 的时候，就慢得几乎永远算不出的时候，就慢得几乎永远算不出结果了。结果了。为什么会这样呢？是因为过多的重复计算。为什么会这样呢？是因为过多的重复计算。我们不妨将对我们不妨将对MaxSum 函数的一次调用称为函数的一次调用称为一次计算。那么，每次计算一次计算。那么，每次计算MaxSum(r, j)的的时候，都要计算一次时候，都要计算一次MaxSum(r+1, j+1)，而每次计算而每次计算MaxSum(r, j+1)的时候，也要的时候，也要计算一次计算一次MaxSum(r+1, j+1)。重复计算因。重复计算因此产生。此产生。在

47、题 目 中 给 出 的 例 子 里 ， 如 果 我 们 将在 题 目 中 给 出 的 例 子 里 ， 如 果 我 们 将MaxSum(r, j)被计算的次数都写在位置（被计算的次数都写在位置（r, j），那么就能得到右面的三角形：），那么就能得到右面的三角形：11 11 2 11 3 3 11 4 6 4 173 88 1 02 7 4 44 5 2 6 5程序分析 n 从上图可以看出，最后一行的计算次数总和是从上图可以看出，最后一行的计算次数总和是16，倒数第二行，倒数第二行的计算次数总和是的计算次数总和是8。不难总结出规律，对于。不难总结出规律，对于N 行的三角形，总行的三角形，总的计算次

48、数是的计算次数是20 +21+22+2(N-1)=2N-1。当。当N= 100 时，总的计算次数是一个让人无法接受的大数字。时，总的计算次数是一个让人无法接受的大数字。n 既然问题出在重复计算，那么解决的办法，当然就是，一个值既然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出一旦算出来，就要记住，以后不必重新计算。即第一次算出MaxSum(r, j)的值时，就将该值存放起来，下次再需要计算的值时，就将该值存放起来，下次再需要计算MaxSum(r, j)时，直接取用存好的值即可，不必再次调用时，直接取用存好的值即可，不必再次调用MaxSum

49、 进行函数递归计算了。这样，每个进行函数递归计算了。这样，每个MaxSum(r, j)都只都只需要计算需要计算1 次即可，那么总的计算次数（即调用次即可，那么总的计算次数（即调用MaxSum 函数的函数的次数）就是三角形中的数字总数，即次数）就是三角形中的数字总数，即1+2+3+N = N(N+1)/2。n 如何存放计算出来的如何存放计算出来的MaxSum（r, j）值呢？显然，用一个二维）值呢？显然，用一个二维数组数组aMaxSumNN就能解决。就能解决。aMaxSumrj就存放就存放MaxSum(r, j)的计算结果。下次再需要的计算结果。下次再需要MaxSum(r, j)的值时，的值时，

50、不必再调用不必再调用MaxSum 函数，只需直接取函数，只需直接取aMaxSumrj的值即的值即可。可。4、参考程序 II#include #include #define MAX_NUM 100int DMAX_NUM + 10MAX_NUM + 10;int N;int aMaxSumMAX_NUM + 10MAX_NUM + 10;int MaxSum( int r, int j) if( r = N ) return Drj; if( aMaxSumr+1j = -1 ) /如果如果MaxSum(r+1, j)没有计算过没有计算过 aMaxSumr+1j = MaxSum(r+1, j

51、); if( aMaxSumr+1j+1 = -1) aMaxSumr+1j+1 = MaxSum(r+1, j+1); if( aMaxSumr+1j aMaxSumr+1j+1 ) return aMaxSumr+1j +Drj; return aMaxSumr+1j+1 + Drj;4、参考程序 IIint main(void) int m; scanf(%d, & N); /将将 aMaxSum 全部置成全部置成-1, 开始时所有的开始时所有的 MaxSum(r, j)都没有算过都没有算过 memset(aMaxSum, -1, sizeof(aMaxSum); for( in

52、t i = 1; i = N; i + ) for( int j = 1; j = i; j + ) scanf(%d, & Dij); printf(%d, MaxSum(1, 1); return 0;程序II分析 这种将一个问题分解为子问题递归求解，并且将中间结果这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做保存以避免重复计算的办法，就叫做“动态规划动态规划”。动态规动态规划通常用来求最优解，能用动态规划解决的求最优解问题，划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。必须满足，最优解的每个局部解

53、也都是最优的。以上题为例，以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。字出发到达到底部的最佳路径。实际上，递归的思想在编程时未必要实现为递归函数。在上实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：面的例子里，有递推公式： Drj rNaMaxSumrjMax(aMaxSumr1j, aMaxSumr1j1)Drj 其其他他因此，不需要写递归函数，从因此，不需要写递归函数，从aMaxSumN-1这一行元素这一行元素开始向上逐行递推，就能求得开始向上逐行递推，就能求得a

54、MaxSum11的值了。的值了。5、参考程序 IIIint DMAX_NUM + 10MAX_NUM + 10;int N;int aMaxSumMAX_NUM + 10MAX_NUM + 10;int main(void) int i, j; scanf(%d, & N); for( i = 1; i = N; i + ) for( j = 1; j = i; j + ) scanf(%d, &Dij); for( j = 1; j 1 ; i - ) for( j = 1; j aMaxSumij+1 ) aMaxSumi-1j = aMaxSumij + Di-1j; e

55、lse aMaxSumi-1j = aMaxSumij+1 + Di-1j; printf(%d, aMaxSum11); return 0;思考题思考题：上面的几个程序：上面的几个程序只算出了最佳路径的数字只算出了最佳路径的数字之和。如果要求输出最佳之和。如果要求输出最佳路径上的每个数字，该怎路径上的每个数字，该怎么办？么办？动态规划解题的一般思路 n 许多求最优解的问题可以用动态规划来解决。许多求最优解的问题可以用动态规划来解决。n 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导首先要把原问题分解为若干个子问题。注意单纯的递归往往会导致子问题被重复计算，用动态规划的方法，子问题的

56、解一旦求出就致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就要被保存，所以每个子问题只需求解一次。要被保存，所以每个子问题只需求解一次。 n 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的从原来的n 变成了变成了n-1，或从原来的，或从原来的nm 变成了变成了n(m-1) 等等等。等。n 找到子问题，就意味着找到了将整个问题逐渐分解的办法。找到子问题，就意味着找到了将整个问题逐渐分解的办法。n 分解下去，直到最底层规模最小的的子问题可以一目了然地看出分解下去，直到最底层规模最小的的子问题可以一目了然地看出解。解

57、。n 每一层子问题的解决，会导致上一层子问题的解决，逐层向上，每一层子问题的解决，会导致上一层子问题的解决，逐层向上，就会导致最终整个问题的解决。就会导致最终整个问题的解决。n 如果从最底层的子问题开始，自底向上地推导出一个个子问题的如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程的时候就不需要写递归函数。解，那么编程的时候就不需要写递归函数。动态规划解题的一般思路 n 用动态规划解题时，将和子问题相关的各个变量的一组取值，用动态规划解题时，将和子问题相关的各个变量的一组取值，称之为一个称之为一个“状态状态”。一个。一个“状态状态”对应于一个或多个子问题，对应于一个或多个子

58、问题，所谓某个所谓某个“状态状态”下的下的“值值”，就是这个，就是这个“状态状态”所对应的子所对应的子问题的解。问题的解。n 比如数字三角形，子问题就是比如数字三角形，子问题就是“从位于从位于(r，j)数字开始，到数字开始，到底边路径的最大和底边路径的最大和”。这个子问题和两个变量。这个子问题和两个变量r 和和j 相关，那相关，那么一个么一个“状态状态”，就是，就是r, j 的一组取值，即每个数字的位置就的一组取值，即每个数字的位置就是一个是一个“状态状态”。该。该“状态状态”所对应的所对应的“值值”，就是从该位置，就是从该位置的数字开始，到底边的最佳路径上的数字之和。的数字开始，到底边的最佳

59、路径上的数字之和。n 定义出什么是定义出什么是“状态状态”，以及在该，以及在该 “状态状态”下的下的“值值”后，后，就要找出不同的状态之间如何迁移就要找出不同的状态之间如何迁移即如何从一个或多个即如何从一个或多个“值值”已知的已知的 “状态状态”，求出另一个，求出另一个“状态状态”的的“值值”。状。状态的迁移可以用递推公式表示，此递推公式也可被称作态的迁移可以用递推公式表示，此递推公式也可被称作“状态状态转移方程转移方程”。动态规划解题的一般思路 n用动态规划解题，如何寻找用动态规划解题，如何寻找“子问题子问题”，定义，定义“状态状态”，“状态转移方程状态转移方程”是什么样的，并没有一定之规，

60、需要具体问是什么样的，并没有一定之规，需要具体问题具体分析，题目做多了就会有感觉。题具体分析，题目做多了就会有感觉。n甚至，对于同一个问题，分解成子问题的办法可能不止一种，甚至，对于同一个问题，分解成子问题的办法可能不止一种，因而因而“状态状态”也可以有不同的定义方法。不同的也可以有不同的定义方法。不同的“状态状态”定义定义方法可能会导致时间、空间效率上的区别。方法可能会导致时间、空间效率上的区别。 Drj rNaMaxSumrjMax(aMaxSumr1j, aMaxSumr1j1)Drj 其其他他最长上升子序列 1、问题描述、问题描述 一个数的序列一个数的序列bi，当，当b1 b2 . bS 的时候，的时候，我们称这个序列是上升的。对于给定的一个序列我们称这个序列是上升的。对于给定的一个序列(a1, a2, ., aN)，我们可以得到一些