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

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

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

3、求出原来问题的解。 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) 递归与分治基本原理 递归、递推、分治 递归与递推表面看来是相逆的过程，其实也是相似的，最终的 计算都是从小算到大。 递推的使用环境要求高导致了递推的高效性，递推没有重复计 算什么数据，保持了高效。 递归大多数会重复计算子问题，导致时间浪费，所以一般不要 使用过深的递归，甚至会空间溢出。 但是也不能说递推好，递归差，因为递归却能解

4、决很多递推做 不到的事情，在某些特定的环境下也能实现高效，并且递归容 易使用。我们要就事论事！ 斐波那契数列（Fibonacci），对于f（30），如果使用递 归则需要运行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

5、种不同的划分： 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+1。 (2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 (1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 n n111 (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的

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

7、p(n)为正整数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个 数记作q(n,m)。可以建立q(n,m)的如下递归关系。 正整数n的划分数p(n)=q(n,n)。 22/38 二叉树二叉树 1、问题描述、问题描述 图图1 满二叉树满二叉树 23/38 问题描述问题描述 如上图所示，由正整数如上图所示，由正整数1, 2, 3, .组成了一棵无限大的二叉组成了一棵无限大的二叉 树。从某一个结点到根结点（编号是树。从某一个结点到根结点（编号是1的结点）都有一条唯一的结点）都有一条唯一 的路径，比如从的路径，比如从10到根结点的路径是到根结点的路径是(10,

8、5, 2, 1)，从，从4到根到根 结点的路径是结点的路径是(4, 2, 1)，从根结点，从根结点1到根结点的路径上只包含到根结点的路径上只包含 一个结点一个结点1，因此路径就是，因此路径就是(1)。 对于两个结点对于两个结点x和和y，假设他们到根结点的路径分别是，假设他们到根结点的路径分别是(x1, x2, . ,1)和和(y1, y2, . ,1)（这里显然有（这里显然有x = x1，y = y1），）， 那么必然存在两个正整数那么必然存在两个正整数i和和j，使得从，使得从xi 和和 yj开始，有开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,

9、. 现在的问题就是，给定现在的问题就是，给定x和和y， 要求要求xi（也就是（也就是yj）。）。 24/38 问题描述问题描述 输入格式输入格式 输入只有一行，包括两个正整数输入只有一行，包括两个正整数x 和和y，这两个正，这两个正 整数都不大于整数都不大于1000。 输出要求输出要求 输出只有一个正整数输出只有一个正整数xi。 输入样例输入样例 10 4 输出样例输出样例 2 25/38 n这个题目要求树上任意两个节点的最近公共子节点。分析这这个题目要求树上任意两个节点的最近公共子节点。分析这 棵树的结构不难看出，不论奇数偶数，每个数对棵树的结构不难看出，不论奇数偶数，每个数对2 做整数除法

10、，做整数除法， 就走到它的上层结点。就走到它的上层结点。 n我们可以每次让较大的一个数（也就是在树上位于较低层次我们可以每次让较大的一个数（也就是在树上位于较低层次 的节点）向上走一个结点，直到两个结点相遇。的节点）向上走一个结点，直到两个结点相遇。 n如果两个节点位于同一层，并且它们不相等，可以让其中任如果两个节点位于同一层，并且它们不相等，可以让其中任 何一个先往上走，然后另一个再往上走，直到它们相遇。何一个先往上走，然后另一个再往上走，直到它们相遇。 n设设common(x, y)表示整数表示整数x 和和y的最近公共子节点，那么，的最近公共子节点，那么， 根据比较根据比较x 和和y 的值

11、，我们得到三种情况：的值，我们得到三种情况： 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)等于等于common(x y/2)； 2、解题思路、解题思路 26/38 3、参考程序、参考程序 n#include nint common(int x, int y) n n if(x = y) n return x; n if(x y) n return common(x / 2, y); n ret

12、urn n common(x, y / 2); n nint main(void) n n int m, n; n scanf(%d%d, n printf(%dn, common(m, n); n return 0; n 27/38 波兰表达式波兰表达式 1、问题描述、问题描述 波兰表达式是一种把运算符前置的算术表达式，例波兰表达式是一种把运算符前置的算术表达式，例 如普通的表达式如普通的表达式2 + 3 的波兰表示法为的波兰表示法为+ 2 3。波。波 兰表达式的优点是运算符之间不必有优先级关系，兰表达式的优点是运算符之间不必有优先级关系， 也不必用括号改变运算次序，例如也不必用括号改变运算

13、次序，例如(2 + 3) * 4 的的 波兰表示法为波兰表示法为* + 2 3 4。本题求解波兰表达式的。本题求解波兰表达式的 值，其中运算符包括值，其中运算符包括 + - * / 四个。四个。 28/38 问题描述问题描述 n 输入数据输入数据 输入为一行，其中运算符和运算数之间都用空格分输入为一行，其中运算符和运算数之间都用空格分 隔，运算数是浮点数隔，运算数是浮点数 n 输出要求输出要求 输出为一行，表达式的值。输出为一行，表达式的值。 n 输入样例输入样例 * + 11.0 12.0 + 24.0 35.0 n 输出样例输出样例 1357.000000 29/38 n这个问题看上去有些

14、复杂，如果只是简单地模拟计算步骤不太这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太 容易想清楚，但是如果用递归的思想就非常容易想清楚。让我容易想清楚，但是如果用递归的思想就非常容易想清楚。让我 们根据逆波兰表达式的定义进行递归求解。在递归函数中，针们根据逆波兰表达式的定义进行递归求解。在递归函数中，针 对当前的输入，有五种情况：对当前的输入，有五种情况： n(1) 输入是常数，则表达式的值就是这个常数；输入是常数，则表达式的值就是这个常数； n(2) 输入是输入是+，则表达式的值是再继续读入两个表达式并计，则表达式的值是再继续读入两个表达式并计 算出它们的值，然后将它们的值相加；算出它

15、们的值，然后将它们的值相加； n(3) 输入是输入是-； n(4) 输入是输入是*； n(5) 输入是输入是/； n后几种情况与后几种情况与2）相同，只是计算从）相同，只是计算从+变成变成- ，*，/。 2、解题思路、解题思路 30/38 3、参考程序、参考程序 n#include n#include ndouble exp(void) n n char a10; n scanf(%s, a); n switch(a0) n n case+: return exp( ) + exp( ); n case-: return exp( ) - exp( ); n case*: return exp

16、( ) * exp( ); n case/: return exp( ) / exp( ); n default: return atof(a); n n 31/38 nint main(void) n n double ans; n ans = exp(); n printf(%f, ans); n return 0; n 32/38 放苹果放苹果 1、问题描述、问题描述 把把 M 个同样的苹果放在个同样的苹果放在N 个同样的盘子个同样的盘子 里，允许有的盘子空着不放，问共有多少种里，允许有的盘子空着不放，问共有多少种 不同的分法？（用不同的分法？（用K 表示）注意：表示）注意：5，1，1

17、和和1，5，1 是同一种分法。是同一种分法。 33/38 问题描述问题描述 n输入数据输入数据 n第一行是测试数据的数目第一行是测试数据的数目t（0 = t = 20）。以下每）。以下每 行均包含两个整数行均包含两个整数M 和和N，以空格分开。，以空格分开。1=M， Nm，必定有，必定有n-m 个盘子永远空着，去掉它们对摆放苹果方法个盘子永远空着，去掉它们对摆放苹果方法 数目不产生影响；即数目不产生影响；即if(nm) f(m,n) =f(m,m)。当。当n m) nreturn f (m, m); nreturnf (m , n-1)+f (m-n , n); n n由上可知：当由上可知：当

18、n=时，所有苹果都必须放在一个盘子里，所以返回时，所有苹果都必须放在一个盘子里，所以返回 ；当没有苹果可放时，定义为种放法；递归的两条路，第一条；当没有苹果可放时，定义为种放法；递归的两条路，第一条n 会逐渐减少，终会到达出口会逐渐减少，终会到达出口n=1; 第二条第二条m 会逐渐减少，因为会逐渐减少，因为 nm 时，我们会时，我们会return f(m , m) 所以终会到达出口所以终会到达出口m=0 n注：苹果注：苹果(相同或不同相同或不同)放入盘子放入盘子(相同或不同相同或不同)的问题，在的问题，在组合数组合数 学学中有更多的论述，可参考卢开澄的中有更多的论述，可参考卢开澄的组合数学组合

19、数学(第第2版版)第第2章章 中的中的Stirling数。数。 36/38 3、参考程序、参考程序 n#include nint count(int x, int y) n n 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); n 37/38 参考程序参考程序 nint main(void) n n int t, m, n; n scanf(%d, n for(int i = 0; i t; i+) n n scanf(%d%d, n

20、 printf(%dn, count(m, n); n n return 0; n 38/38 红与黑红与黑 1、问题描述、问题描述 有一间长方形的房子，地上铺了红色、黑色两有一间长方形的房子，地上铺了红色、黑色两 种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖 上，只能向相邻的黑色瓷砖移动。请写一个程序，上，只能向相邻的黑色瓷砖移动。请写一个程序， 计算你总共能够到达多少块黑色的瓷砖。计算你总共能够到达多少块黑色的瓷砖。 39/38 问题描述问题描述 n输入数据输入数据 n包括多个数据集合。每个数据集合的第一行是两个整数包括多个数据集合。每个数据集合

21、的第一行是两个整数 W 和和H，分别表示，分别表示x 方向和方向和y 方向瓷砖的数量。方向瓷砖的数量。W 和和H 都不超过都不超过20。在接下来的。在接下来的H 行中，每行包括行中，每行包括W 个字符。个字符。 每个字符表示一块瓷砖的颜色，规则如下每个字符表示一块瓷砖的颜色，规则如下 n(1).：黑色的瓷砖；：黑色的瓷砖； n(2)#：红色的瓷砖；：红色的瓷砖； n(3)：黑色的瓷砖，并且你站在这块瓷砖上。该字符：黑色的瓷砖，并且你站在这块瓷砖上。该字符 在每个数据集合中唯一出现一次。在每个数据集合中唯一出现一次。 n当在一行中读入的是两个零时，表示输入结束。当在一行中读入的是两个零时，表示输

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

23、走时，可能遇到的三种情况：出了矩阵边界、遇到右行走时，可能遇到的三种情况：出了矩阵边界、遇到.、遇、遇 到到#。 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这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过 每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。 2、解题思路、解题思

24、路 42/38 3、参考程序、参考程序 n#include nint W, H; nchar z2121; nint f(int x, int y) n n if(x = W | y = H) / 如果走出矩阵范围如果走出矩阵范围 n return 0; n if(zxy = #) n return 0; n else n n zxy = #; / 将走过的瓷砖做标记将走过的瓷砖做标记 n return 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1); n n 43/38 参考程序参考程序 nint main(void) n

25、n int i, j, num; n while(scanf(%d %d, 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; n divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (

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

27、问题以及用merge将k个子问题的解合 并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解 规模为|P|=n的问题所需的计算时间，则有： 1 1 )()/( ) 1 ( )( n n nfmnkT O nT 通过迭代法求得方程的解： 1log 0 log )/()( n m j jj k m mnfknnT 注意注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但 是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值 可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而 当minmi+1时，T(mi)T(n)T(mi+1)。 分析：如果n=1即只有一个元素

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

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

30、earch(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) 时间， 因此整

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

32、数的乘法运算 u小学的方法：O(n2) 效率太低 u分治法: XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度，必须减少乘法的次数。 XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd 1.XY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd 复杂度分析复杂度分析 T(n)=O(nlog3) =O(n1.59) 较大的改进较大的改进 1 1 )()2/(3 ) 1 ( )( n n nOnT O nT 细节问题细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可 能得到m+1位的结果，

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

34、Ci,j定义为: n k jkBkiAjiC 1 若依此定义来计算A和B的乘积矩阵C，则每计 算C的一个元素Cij，需要做n次乘法和n-1次 加法。因此，算出矩阵C的 个元素所需的计算 时间为O(n3) u传统方法：O(n3) 使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4 个大小相等的子矩阵。由此可将方程C=AB重写为： u传统方法：O(n3) u分治法: 2221 1211 2221 1211 2221 1211 BB BB AA AA CC CC 由此可得： 2112111111 BABAC 2212121112 BABAC 2122112121 BABAC 22221221

35、22 BABAC 复杂度分析复杂度分析 T(n)=O(n3) 没有改进没有改进 2 2 )()2/(8 ) 1 ( )( 2 n n nOnT O nT u传统方法：O(n3) u分治法: 为了降低时间复杂度，必须减少乘法的次数。 2221 1211 2221 1211 2221 1211 BB BB AA AA CC CC )( 2212111 BBAM 2212112 )(BAAM 1122213 )(BAAM )( 1121224 BBAM )( 221122115 BBAAM )( 222122126 BBAAM )( 121121117 BBAAM 624511 MMMMC 2112

36、 MMC 4321 MMC 731522 MMMMC 复杂度分析复杂度分析 T(n)=O(nlog7) =O(n2.81) 较大的改进较大的改进 2 2 )()2/(7 ) 1 ( )( 2 n n nOnT O nT u传统方法：O(n3) u分治法: O(n2.81) u更快的方法? Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘 积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时 间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法 了。或许应当研究或矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复 杂性。目前最好的计算时间上界是 O

37、(n2.376) 是否能找到O(n2)的算法？目前为止还没有结果。 private static int partition (int p, int r) int i = p, j = r + 1; Comparable x = ap; / 将= x的元素交换到左边区域 / 将= x的元素交换到右边区域 while (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, 8 j-; j i 5, 7, 5, 2, 6,

38、 8 i+; j i 5, 6, 5, 2, 7, 8 j-; j i 5, 2, 5, 6, 7, 8 i+; ji 完成 快速排序具有不稳定性不稳定性。 6, 7, 5, 2, 5, 8 5, 2, 5 6 7, 8 private static int randomizedPartition (int p, int r) int i = random(p,r); MyMath.swap(a, i, p); return partition (p, r); 快速排序算法的性能取决于划分的对称性。通过修改 算法partition，可以设计出采用随机选择策略的快速排 序算法。在快速排序算法的每

39、一步中，当数组还没有被 划分时，可以在ap:r中随机选出一个元素作为划分基准， 这样可以使划分基准的选择是随机的，从而可以期望划 分是较对称的。 int N; int MaxSum( int r, int j) if( r = N ) return Drj; int nSum1 = MaxSum(r+1, j); int nSum2 = MaxSum(r+1, j+1); if( nSum1 nSum2 ) return nSum1+Drj; return nSum2+Drj; 3、参考程序 I int main(void) int m; scanf(%d, for( int i = 1; i

40、 = N; i + ) for( int j = 1; j = i; j + ) scanf(%d, printf(%d, MaxSum(1, 1); return 0; 提交结果：提交结果：Time Limit Exceed 程序I分析 上面的程序，效率非常低，在上面的程序，效率非常低，在N 值并不大，值并不大， 比如比如N=100 的时候，就慢得几乎永远算不出的时候，就慢得几乎永远算不出 结果了。结果了。 为什么会这样呢？是因为过多的重复计算。为什么会这样呢？是因为过多的重复计算。 我们不妨将对我们不妨将对MaxSum 函数的一次调用称为函数的一次调用称为 一次计算。那么，每次计算一次计算

41、。那么，每次计算MaxSum(r, j)的的 时候，都要计算一次时候，都要计算一次MaxSum(r+1, j+1)， 而每次计算而每次计算MaxSum(r, j+1)的时候，也要的时候，也要 计算一次计算一次MaxSum(r+1, j+1)。重复计算因。重复计算因 此产生。此产生。 在 题 目 中 给 出 的 例 子 里 ， 如 果 我 们 将在 题 目 中 给 出 的 例 子 里 ， 如 果 我 们 将 MaxSum(r, j)被计算的次数都写在位置（被计算的次数都写在位置（r, j），那么就能得到右面的三角形：），那么就能得到右面的三角形： 1 1 1 1 2 1 1 3 3 1 1 4

42、6 4 1 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 程序分析 n 从上图可以看出，最后一行的计算次数总和是从上图可以看出，最后一行的计算次数总和是16，倒数第二行，倒数第二行 的计算次数总和是的计算次数总和是8。不难总结出规律，对于。不难总结出规律，对于N 行的三角形，总行的三角形，总 的计算次数是的计算次数是20 +21+22+2(N-1)=2N-1。当。当 N= 100 时，总的计算次数是一个让人无法接受的大数字。时，总的计算次数是一个让人无法接受的大数字。 n 既然问题出在重复计算，那么解决的办法，当然就是，一个值既然问题出在重复计算，那么解决的办法，当然就是，一个值

43、 一旦算出来，就要记住，以后不必重新计算。即第一次算出一旦算出来，就要记住，以后不必重新计算。即第一次算出 MaxSum(r, j)的值时，就将该值存放起来，下次再需要计算的值时，就将该值存放起来，下次再需要计算 MaxSum(r, j)时，直接取用存好的值即可，不必再次调用时，直接取用存好的值即可，不必再次调用 MaxSum 进行函数递归计算了。这样，每个进行函数递归计算了。这样，每个MaxSum(r, j)都只都只 需要计算需要计算1 次即可，那么总的计算次数（即调用次即可，那么总的计算次数（即调用MaxSum 函数的函数的 次数）就是三角形中的数字总数，即次数）就是三角形中的数字总数，即

44、1+2+3+N = N(N+1)/2。 n 如何存放计算出来的如何存放计算出来的MaxSum（r, j）值呢？显然，用一个二维）值呢？显然，用一个二维 数组数组aMaxSumNN就能解决。就能解决。aMaxSumrj就存放就存放 MaxSum(r, j)的计算结果。下次再需要的计算结果。下次再需要MaxSum(r, j)的值时，的值时， 不必再调用不必再调用MaxSum 函数，只需直接取函数，只需直接取aMaxSumrj的值即的值即 可。可。 4、参考程序 II #include #include #define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 1

45、0; 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); if( aMaxSumr+1j+1 = -1) aMaxSumr+1j+1 = MaxSum(r+1, j+1); if( aMaxSumr+1j aMaxSumr+1j+1 ) return aMaxSumr+1j +Drj; retur

46、n aMaxSumr+1j+1 + Drj; 4、参考程序 II int main(void) int m; scanf(%d, /将将 aMaxSum 全部置成全部置成-1, 开始时所有的开始时所有的 MaxSum(r, j)都没有算过都没有算过 memset(aMaxSum, -1, sizeof(aMaxSum); for( int i = 1; i = N; i + ) for( int j = 1; j = i; j + ) scanf(%d, printf(%d, MaxSum(1, 1); return 0; 程序II分析 这种将一个问题分解为子问题递归求解，并且将中间结果这种将

47、一个问题分解为子问题递归求解，并且将中间结果 保存以避免重复计算的办法，就叫做保存以避免重复计算的办法，就叫做“动态规划动态规划”。动态规动态规 划通常用来求最优解，能用动态规划解决的求最优解问题，划通常用来求最优解，能用动态规划解决的求最优解问题， 必须满足，最优解的每个局部解也都是最优的。必须满足，最优解的每个局部解也都是最优的。以上题为例，以上题为例， 最佳路径上面的每个数字到底部的那一段路径，都是从该数最佳路径上面的每个数字到底部的那一段路径，都是从该数 字出发到达到底部的最佳路径。字出发到达到底部的最佳路径。 实际上，递归的思想在编程时未必要实现为递归函数。在上实际上，递归的思想在编

48、程时未必要实现为递归函数。在上 面的例子里，有递推公式：面的例子里，有递推公式： Drj rN aMaxSumrj Max(aMaxSumr1j, aMaxSumr1j1)Drj 其其他他 因此，不需要写递归函数，从因此，不需要写递归函数，从aMaxSumN-1这一行元素这一行元素 开始向上逐行递推，就能求得开始向上逐行递推，就能求得aMaxSum11的值了。的值了。 5、参考程序 III int DMAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; int main(void) int i, j; sca

49、nf(%d, for( i = 1; i = N; i + ) for( j = 1; j = i; j + ) scanf(%d, for( j = 1; j 1 ; i - ) for( j = 1; j aMaxSumij+1 ) aMaxSumi-1j = aMaxSumij + Di-1j; else aMaxSumi-1j = aMaxSumij+1 + Di-1j; printf(%d, aMaxSum11); return 0; 思考题思考题：上面的几个程序：上面的几个程序 只算出了最佳路径的数字只算出了最佳路径的数字 之和。如果要求输出最佳之和。如果要求输出最佳 路径上的每个

50、数字，该怎路径上的每个数字，该怎 么办？么办？ 动态规划解题的一般思路 n 许多求最优解的问题可以用动态规划来解决。许多求最优解的问题可以用动态规划来解决。 n 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导首先要把原问题分解为若干个子问题。注意单纯的递归往往会导 致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就 要被保存，所以每个子问题只需求解一次。要被保存，所以每个子问题只需求解一次。 n 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模子问题经常和原问题形式相似，有时甚至完全一样，只不过规模 从原来的从

51、原来的n 变成了变成了n-1，或从原来的，或从原来的nm 变成了变成了n(m-1) 等等 等。等。 n 找到子问题，就意味着找到了将整个问题逐渐分解的办法。找到子问题，就意味着找到了将整个问题逐渐分解的办法。 n 分解下去，直到最底层规模最小的的子问题可以一目了然地看出分解下去，直到最底层规模最小的的子问题可以一目了然地看出 解。解。 n 每一层子问题的解决，会导致上一层子问题的解决，逐层向上，每一层子问题的解决，会导致上一层子问题的解决，逐层向上， 就会导致最终整个问题的解决。就会导致最终整个问题的解决。 n 如果从最底层的子问题开始，自底向上地推导出一个个子问题的如果从最底层的子问题开始，

52、自底向上地推导出一个个子问题的 解，那么编程的时候就不需要写递归函数。解，那么编程的时候就不需要写递归函数。 动态规划解题的一般思路 n 用动态规划解题时，将和子问题相关的各个变量的一组取值，用动态规划解题时，将和子问题相关的各个变量的一组取值， 称之为一个称之为一个“状态状态”。一个。一个“状态状态”对应于一个或多个子问题，对应于一个或多个子问题， 所谓某个所谓某个“状态状态”下的下的“值值”，就是这个，就是这个“状态状态”所对应的子所对应的子 问题的解。问题的解。 n 比如数字三角形，子问题就是比如数字三角形，子问题就是“从位于从位于(r，j)数字开始，到数字开始，到 底边路径的最大和底边

53、路径的最大和”。这个子问题和两个变量。这个子问题和两个变量r 和和j 相关，那相关，那 么一个么一个“状态状态”，就是，就是r, j 的一组取值，即每个数字的位置就的一组取值，即每个数字的位置就 是一个是一个“状态状态”。该。该“状态状态”所对应的所对应的“值值”，就是从该位置，就是从该位置 的数字开始，到底边的最佳路径上的数字之和。的数字开始，到底边的最佳路径上的数字之和。 n 定义出什么是定义出什么是“状态状态”，以及在该，以及在该 “状态状态”下的下的“值值”后，后， 就要找出不同的状态之间如何迁移就要找出不同的状态之间如何迁移即如何从一个或多个即如何从一个或多个 “值值”已知的已知的

54、“状态状态”，求出另一个，求出另一个“状态状态”的的“值值”。状。状 态的迁移可以用递推公式表示，此递推公式也可被称作态的迁移可以用递推公式表示，此递推公式也可被称作“状态状态 转移方程转移方程”。 动态规划解题的一般思路 n用动态规划解题，如何寻找用动态规划解题，如何寻找“子问题子问题”，定义，定义“状态状态”， “状态转移方程状态转移方程”是什么样的，并没有一定之规，需要具体问是什么样的，并没有一定之规，需要具体问 题具体分析，题目做多了就会有感觉。题具体分析，题目做多了就会有感觉。 n甚至，对于同一个问题，分解成子问题的办法可能不止一种，甚至，对于同一个问题，分解成子问题的办法可能不止一

55、种， 因而因而“状态状态”也可以有不同的定义方法。不同的也可以有不同的定义方法。不同的“状态状态”定义定义 方法可能会导致时间、空间效率上的区别。方法可能会导致时间、空间效率上的区别。 Drj rN aMaxSumrj Max(aMaxSumr1j, aMaxSumr1j1)Drj 其其他他 最长上升子序列 1、问题描述、问题描述 一个数的序列一个数的序列bi，当，当b1 b2 . bS 的时候，的时候， 我们称这个序列是上升的。对于给定的一个序列我们称这个序列是上升的。对于给定的一个序列(a1, a2, ., aN)，我们可以得到一些上升的子序列，我们可以得到一些上升的子序列(ai1, ai

56、2, ., aiK)，这里，这里1 = i1 i2 . iK = N。 比如，对于序列比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上，有它的一些上 升子序列，如升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中等等。这些子序列中 最长的长度是最长的长度是4，比如子序列，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序你的任务，就是对于给定的序列，求出最长上升子序 列的长度。列的长度。 问题描述 输入数据输入数据 输入的第一行是序列的长度输入的第一行是序列的长度N (1 = N = 1000)。第二行。第二行 给出序列中的

57、给出序列中的N 个整数，这些整数的取值范围都在个整数，这些整数的取值范围都在0 到到10000。 输出要求输出要求 最长上升子序列的长度。最长上升子序列的长度。 输入样例输入样例 7 1 7 3 5 9 4 8 输出样例输出样例 4 2、解题思路 n 如何把这个问题分解成子问题呢？经过分析，发现如何把这个问题分解成子问题呢？经过分析，发现 “求以求以 ak（k=1, 2, 3N）为终点的最长上升子序列的长度）为终点的最长上升子序列的长度”是个是个 好的子问题好的子问题这里把一个上升子序列中最右边的那个数，称这里把一个上升子序列中最右边的那个数，称 为该子序列的为该子序列的“终点终点”。虽然这个

58、子问题和原问题形式上并不。虽然这个子问题和原问题形式上并不 完全一样，但是只要这完全一样，但是只要这N 个子问题都解决了，那么这个子问题都解决了，那么这N 个子问个子问 题的解中，最大的那个就是整个问题的解。题的解中，最大的那个就是整个问题的解。 n 由上所述的子问题只和一个变量相关，就是数字的位置。因由上所述的子问题只和一个变量相关，就是数字的位置。因 此序列中数的位置此序列中数的位置k 就是就是“状态状态”，而状态，而状态 k 对应的对应的“值值”， 就是以就是以ak 做为做为“终点终点”的最长上升子序列的长度。这个问题的最长上升子序列的长度。这个问题 的状态一共有的状态一共有N 个。状态

59、定义出来后，转移方程就不难想了。个。状态定义出来后，转移方程就不难想了。 2、解题思路 n假定假定MaxLen (k)表示以表示以ak 做为做为“终点终点”的最长上升子序列的最长上升子序列 的长度，那么：的长度，那么： nMaxLen (1) = 1 nMaxLen (k) = Max MaxLen (i)：1i k 且且 ai ak 且且 k1 + 1 n这个状态转移方程的意思就是，这个状态转移方程的意思就是，MaxLen(k)的值，就是在的值，就是在ak 左边，左边，“终点终点”数值小于数值小于ak，且长度最大的那个上升子序列的，且长度最大的那个上升子序列的 长度再加长度再加1。因为。因为

60、ak 左边任何左边任何“终点终点”小于小于ak 的子序列，加的子序列，加 上上ak 后就能形成一个更长的上升子序列。后就能形成一个更长的上升子序列。 n实 际 实 现 的 时 候 ， 可 以 不 必 编 写 递 归 函 数 ， 因 为 从实 际 实 现 的 时 候 ， 可 以 不 必 编 写 递 归 函 数 ， 因 为 从 MaxLen(1)就能推算出就能推算出MaxLen(2)，有了，有了MaxLen(1)和和 MaxLen(2)就能推算出就能推算出MaxLen(3) 3、参考程序 int bMAX_N + 10; int aMaxLenMAX_N + 10; int main(void)