《第十三周递归与动态规划二》由会员分享，可在线阅读，更多相关《第十三周递归与动态规划二（34页珍藏版）》请在金锄头文库上搜索。
1、厦箩蝇说斧穿肇谎脉配跺堕隐拷霖部嫩颗藩纠遮校绢许擂因筒忙糕絮兔羡第十三周递归与动态规划二第十三周递归与动态规划二第十三讲第十三讲递归与动态规划递归与动态规划(二二)ACMACM算法与程序设计算法与程序设计察蔷隔矫瞥显援骏氛娱筒强道肺凰侵殉种瓜纫轿荚砾掸艰滩芒域构敷甜唱第十三周递归与动态规划二第十三周递归与动态规划二八皇后问题八皇后问题1、链接地址、链接地址 http:/ 2、问题描述、问题描述 会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有个皇后放在棋盘上（有
2、8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。问题。 对于某个满足要求的对于某个满足要求的8皇后的摆放方法，定义一个皇后串皇后的摆放方法，定义一个皇后串a与之对应，即与之对应，即a=b1b2.b8，其中，其中bi为相应摆法中第为相应摆法中第i行皇后行皇后所处的列数。已经知道所处的列数。已经知道8皇后问题一共有皇后问题一共有92组解（即组解（即92个不个不同的皇后串）。同的皇后串）。 给出一个数给出一个数b，要求输出第，要求输出第b个串。串的比较是这样的：皇个串。串的比较是这样的：皇后串后串x置于皇后串置于皇后串y之前，当且仅
3、当将之前，当且仅当将x视为整数时比视为整数时比y小。小。 却啼额嗅章凉遥圆番芬推稠吉近兼形康粘溉游证宫期撞浸素收敬傣捆蔑敬第十三周递归与动态规划二第十三周递归与动态规划二2问题描述问题描述n输入数据输入数据n第第 1 行行是是测测试试数数据据的的组组数数n，后后面面跟跟着着n 行行输输入入。每每组组测测试试数数据占据占1 行，包括一个正整数行，包括一个正整数b(1 = b = 92)n输出要求输出要求nn 行行，每每行行输输出出对对应应一一个个输输入入。输输出出应应是是一一个个正正整整数数，是是对对应于应于b 的皇后串的皇后串n输入样例输入样例n2n1n92n输出样例输出样例n15863724
4、n84136275披肄充珠糕柒尔恒串删捕酗益尘帮艾剩琴土窜蚌钧总悲殊掷甫毒叮狭赊闻第十三周递归与动态规划二第十三周递归与动态规划二3n因为要求出因为要求出 92 种不同摆放方法中的任意一种，所以我们不妨种不同摆放方法中的任意一种，所以我们不妨把把92 种不同的摆放方法一次性求出来，存放在一个数组里。种不同的摆放方法一次性求出来，存放在一个数组里。n为求解这道题我们需要有一个矩阵仿真棋盘，每次试放一个棋为求解这道题我们需要有一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记
5、，如此下去把八个棋子就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。当完成一种摆放时，就要尝试下一种。放好。当完成一种摆放时，就要尝试下一种。n若要按照字典序将可行的摆放方法记录下来，就要按照一定的若要按照字典序将可行的摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试；顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试；对于第一个棋子的每一个位置，将第二个棋子从可行的位置从对于第一个棋子的每一个位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一第二个棋子固定的情况下，将第三小到大的顺序尝试；在第一第二个棋子固定的情况下，将第三个棋子从
6、可行的位置从小到大的顺序尝试；依次类推。个棋子从可行的位置从小到大的顺序尝试；依次类推。3、解题思路、解题思路(一一)怂碑哭骤薄划茵也索士余在夜零盆琢洱阂甚牺统汲微陆汾叔浊蘑湃含父负第十三周递归与动态规划二第十三周递归与动态规划二4n首先，我们有一个首先，我们有一个8*8 的矩阵仿真棋盘标识当前已经摆放好的矩阵仿真棋盘标识当前已经摆放好的棋子所控制的区域。用一个有的棋子所控制的区域。用一个有92 行每行行每行8 个元素的二维数组个元素的二维数组记录可行的摆放方法。用一个递归程序来实现尝试摆放的过程。记录可行的摆放方法。用一个递归程序来实现尝试摆放的过程。n基本思想是假设我们将第一个棋子摆好，并
7、设置了它所控制的基本思想是假设我们将第一个棋子摆好，并设置了它所控制的区域，则这个问题变成了一个区域，则这个问题变成了一个7 皇后问题，用与皇后问题，用与8 皇后同样的皇后同样的方法可以获得问题的解。那我们就把重心放在如何摆放一个皇方法可以获得问题的解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：后棋子上，摆放的基本步骤是：n从第从第1 到第到第8 个位置，顺序地尝试将棋子放置在每一个未被控个位置，顺序地尝试将棋子放置在每一个未被控制的位置上，设置该棋子所控制的格子，将问题变为更小规模制的位置上，设置该棋子所控制的格子，将问题变为更小规模的问题向下递归，需要注意的是每次尝试一个
8、新的未被控制的的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。位置前，要将上一次尝试的位置所控制的格子复原。3、解题思路、解题思路(一一)镑最瓶旗颠青句佯协霹垂惧赂壮赊衔祝佛弊婉瘪抢扬身侨绩毯剁鸥谰搅断第十三周递归与动态规划二第十三周递归与动态规划二54、参考程序、参考程序(一一)n#include n#include nint queenPlaces928; /存放种皇后棋子的摆放方法存放种皇后棋子的摆放方法nint count = 0;nint board88; /仿真棋盘仿真棋盘nvoid putQueen(int ithQueen);
9、 /递归函数，每次摆好一个棋子递归函数，每次摆好一个棋子nint main(void)nn int n, i, j;n for(i = 0; i 8; i+) / 初始化初始化n for(j = 0; j 8; j+) boardij = -1;n for(j = 0; j 92; j+) queenPlacesji = 0;n n putQueen(0); /开始摆放，运行的结果是将开始摆放，运行的结果是将queenPlaces 生成好生成好n scanf(%d, &n);n for(i = 0; i n; i+)n int ith;n scanf(%d, &ith);n for(j = 0
10、; j 8; j+) printf(%d, queenPlacesith - 1j);n printf(n);n n return 0;n要肆毗卸苦痈摔虞缺纱戒毋疑浑啡赔栓骆到蛔权衰况残捐摊帖栋烬陋刷颤第十三周递归与动态规划二第十三周递归与动态规划二64、参考程序、参考程序(一一)nvoid putQueen(int ithQueen) nn int i, k, r;n if(ithQueen = 8)n count +;n return;n n for(i = 0; i 8; i+)n if(boardithQueeni = -1)n boardithQueeni = ithQueen; /
11、摆放皇后摆放皇后n for(k = count; k 92; k+)n queenPlaceskithQueen = i + 1;n for(r = 0; r 8; r+) /设置控制范围设置控制范围n for(k = 0; k 8; k+)n if(boardrk = -1 &(r = ithQueen | k = i n | abs(r - ithQueen) = abs(k - i)n boardrk = ithQueen;n putQueen(ithQueen + 1); /向下级递归向下级递归n for(r = 0; r 8; r+) /回溯，撤销控制范围回溯，撤销控制范围n for
12、(k = 0; k 8; k+)n if(boardrk = ithQueen) boardrk = -1;n n n挡瀑钱慕鹰枪便见倦寥膛揍占慨驯淤扁猿教缘骨亨爵窜市亡擒虹葛驶温裸第十三周递归与动态规划二第十三周递归与动态规划二7n 上上面面的的方方法法用用一一个个二二维维数数组组来来记记录录棋棋盘盘被被已已经经放放置置的的棋棋子子的的控控制制情情况况，每每次次有有新新的的棋棋子子放放置置时时用用了了枚枚举举法法来来判判断断它它控控制制的的范围。范围。n 还还可可以以用用三三个个一一维维数数组组来来分分别别记记录录每每一一列列，每每个个45 度度的的斜斜线线和和每每个个135 度度的的斜斜线
13、线上上是是否否已已经经被被已已放放置置的的棋棋子子控控制制，这这样样每每次次有有新新的的棋棋子子放放置置时时，不不必必再再搜搜索索它它的的控控制制范范围围，可可以以直直接接通通过过三三个个一一维维数数组组判判断断它它是是否否与与已已经经放放置置的的棋棋子子冲冲突突，在在不不冲冲突突的的情情况况下下，也也可可以以通通过过分分别别设设置置三三个个一一维维数数组组的的相相应应的的值值，来来记录新棋子的控制范围。记录新棋子的控制范围。5、解题思路、解题思路(二二)二估鞋甚掖方到茎惰每笼捌怜滋宪卖赵哪申言羽蹦蔓肾蜜逮赢罕嘴暂诞撤第十三周递归与动态规划二第十三周递归与动态规划二86、参考程序、参考程序(二
14、二)n#include nint record939, mark9, count = 1; /record 记录全部解，记录全部解，mark 记录当记录当前解；前解；nbool range9, line117, line217; /分别记录列方向，分别记录列方向，45度，度，135度方向度方向上被控制的情况上被控制的情况nvoid tryToPut(int ); /求全部解的过程求全部解的过程nint main(void)nn int i, testtimes, num;n scanf(%d, &testtimes);n for(i = 0; i =8; i+)n rangei = true;
15、n for(i = 0; i 17; i +)n line1i = line2i = true;n tryToPut(1); /从第一个皇后开始放置从第一个皇后开始放置n while(testtimes -)n n scanf(%d, &num);n for(i = 1; i 8)n /如果最后一个皇后被放置完毕，将当前解复制到全部解中如果最后一个皇后被放置完毕，将当前解复制到全部解中n for(int k = 1; k = 8; k +)n recordcountk = markk;n count +;n n for(int j=1; j=8; j+)n /逐一尝试将当前皇后放置在不同列上逐
16、一尝试将当前皇后放置在不同列上n if(rangej & line1 i + j & line2i - j + 9) /如果与前面不冲突如果与前面不冲突n n marki = j;n rangej = line1i + j = line2i - j + 9 = false;n tryToPut(i + 1);n rangej = line1i + j = line2i - j + 9 = true;/回溯，撤销控制回溯，撤销控制n n n你耶族椅仗蛛捆促处邮擦穷撑鹰外众妇例些粳欺碘主训裸叫苔时矗操禹畏第十三周递归与动态规划二第十三周递归与动态规划二10 这这个个题题目目也也可可以以不不用用仿仿
17、真真棋棋盘盘来来模模拟拟已已放放置置棋棋子子的的控控制制区区域域，而而只只用用一一个个有有8 个个元元素素的的数数组组记记录录已已经经摆摆放放的的棋棋子子摆摆在在什什么么位位置置，当当要要放放置置一一个个新新的的棋棋子子时时，只只需需要要判判断断它它与与已已经经放放置置的的棋棋子子之之间间是是否否冲冲突突就就行了。行了。7、解题思路、解题思路(三三)昧仟涩稀碎沂隔冶胚牵舅辕筛谊辫硅音焚界抢钥续范侄扼捕稿婴寥屡骸著第十三周递归与动态规划二第十三周递归与动态规划二118、参考程序、参考程序(三三)n#include nint ans928, num=0, huang8;nvoid queen(in
18、t i)nn int j, k;n if(i = 8) /一组新的解产生了一组新的解产生了n n for(j = 0; j 8; j+) ansnumj = huangj + 1;n num+;n return;n n for (j=0; j8; j+) /将当前皇后将当前皇后i 逐一尝试放置在不同的列逐一尝试放置在不同的列n n for(k=0; ki; k+) /逐一判定逐一判定i 与前面的皇后是否冲突与前面的皇后是否冲突n if( huangk = j | (k - i) = (huangk - j) n | (i - k) = (huangk - j )n break;n if (k
19、= i) /放置放置i，尝试第，尝试第i+1 个皇后个皇后n n huangi = j;n queen(i + 1);n n n奴评撕央彻搐升秩卉劝獭暖鞍恩怀出爵卡授鹏焙耳瑞克陇驰快敢迫揭傣皿第十三周递归与动态规划二第十三周递归与动态规划二128、参考程序、参考程序(二二)nint main(void)nn int i, j, b, n;n queen(0);n scanf(%d, &n);n for(i = 0; i n; i+)n n scanf(%d, &b);n for(j = 0; j 8; j+)n printf(%d, ansb - 1j);n printf(n);n n ret
20、urn 0;n反绥求吾冲词邑虐毋鹿此恼黍姆弧檄魏纹掇抑浩霓岁它影闻炼五爽冲疽扩第十三周递归与动态规划二第十三周递归与动态规划二13数字三角形数字三角形 1、问题描述、问题描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。路径上的数字之和。注意：路径上的每一步只能从一个数走到下一层上和它最近的注意：路径
21、上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。左边的数或者右边的数。拯首旬转氧奏镇音酚精蛊擞模胎飘告吧啼椽舵哆朴功享翰蓬坊以画搽历赔第十三周递归与动态规划二第十三周递归与动态规划二14问题描述问题描述输入数据输入数据输入的第一行是一个整数输入的第一行是一个整数N (1 N = 100)，给出，给出三角形的行数。下面的三角形的行数。下面的N 行给出数字三角形。数字三行给出数字三角形。数字三角形上的数的范围都在角形上的数的范围都在0 和和100 之间。之间。输出要求输出要求输出最大的和。输出最大的和。斯滔懂熄口兆询妓辊吓悄其前笼甭嫉叼腰窘诗捞琳胶爽眼蒲懂淳塔轧天玻第十三周递归与
22、动态规划二第十三周递归与动态规划二15问题描述问题描述输入样例输入样例573 88 1 02 7 4 44 5 2 6 5输出样例输出样例30绘漫伎厨惯篆铡拷戮肚响饼陀宦窟磊狼嘿秀行能恍尔锯融钠奢瓜送龟辨抛第十三周递归与动态规划二第十三周递归与动态规划二162、解题思路解题思路 这道题目可以用递归的方法解决。基本思路是：这道题目可以用递归的方法解决。基本思路是：以以D( r, j)表示第表示第r 行第行第 j 个数字个数字(r，j 都从都从1 开始算开始算)，以，以MaxSum(r, j) 代表从第代表从第 r 行的第行的第 j 个数字到底边的最佳路径个数字到底边的最佳路径的数字之和，则本题是
23、要求的数字之和，则本题是要求 MaxSum(1, 1) 。从某个从某个D(r, j)出发，显然下一步只能走出发，显然下一步只能走D(r+1, j)或者或者D(r+1, j+1)。如果走。如果走D(r+1, j)，那么得到的，那么得到的MaxSum(r, j)就是就是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)哪个更大了。哪个更大了。
24、耗陀烷描霓盈挠须敦完怠珠堕月拢玛斥闺癸诛磋誉通织侍人卒凉利钧噎嘉第十三周递归与动态规划二第十三周递归与动态规划二173、参考程序参考程序 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 = MaxSum(r+1, j);int nSum2 = MaxSum(r+1, j+1);if( nSum1 nSum2 )return nSum1+Drj;return nSum2+Drj; 帆差唬瓶肾誓贷癌戌烃愧
25、侠狐竞摸筑虑熊爱役约些处邓展东辆脖藉瓶始衍第十三周递归与动态规划二第十三周递归与动态规划二183、参考程序参考程序 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者凿杜侈莹抄糕钩痒降疡飘杰技怯众帘妒等辉沸嘎给周妹缅周楔酬疽畴陈第十三周递归与动态规划二第十三周递归与动态规划二19程序程序I分析分析 上上面面的的程
26、程序序，效效率率非非常常低低，在在N 值值并并不不大大，比比如如N=100 的的时时候候，就就慢慢得得几几乎乎永永远远算算不不出出结果了。结果了。为什么会这样呢？是因为过多的重复计算。为什么会这样呢？是因为过多的重复计算。我我们们不不妨妨将将对对MaxSum 函函数数的的一一次次调调用用称称为为一一次次计计算算。那那么么，每每次次计计算算MaxSum(r, j)的的时时候候，都都要要计计算算一一次次MaxSum(r+1, j+1)，而而每每次次计计算算MaxSum(r, j+1)的的时时候候，也也要要计计算算一一次次MaxSum(r+1, j+1)。重重复复计计算算因因此产生。此产生。在在 题
27、题 目目 中中 给给 出出 的的 例例 子子 里里 ， 如如 果果 我我 们们 将将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次耍烹睬申崩傻涨枢洗卜薯卡铰查闷荔规国斥户幢韧留邀移最或畜商裸抉第十三周递归与动态规划二第十三周递归与动态规划二20程序分析 n 从上图可以看出，最后一行的计算次数总和是从上图可以看出，最后一行的计算次数总和是16，倒数第二行，倒数第二行的计算次数总和是的计算次数总和是8。不难
28、总结出规律，对于。不难总结出规律，对于N 行的三角形，总的行的三角形，总的计算次数是计算次数是20 +21+22+2(N-1)=2N-1。当。当N= 100 时，总的计算次数是一个让人无法接受的大数字。时，总的计算次数是一个让人无法接受的大数字。n 既然问题出在重复计算，那么解决的办法，当然就是，一个值既然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出一旦算出来，就要记住，以后不必重新计算。即第一次算出MaxSum(r, j)的值时，就将该值存放起来，下次再需要计算的值时，就将该值存放起来，下次再需要计算MaxSum(r, j)时，直接取
29、用存好的值即可，不必再次调用时，直接取用存好的值即可，不必再次调用MaxSum 进行函数递归计算了。这样，每个进行函数递归计算了。这样，每个MaxSum(r, j)都只都只需要计算需要计算1 次即可，那么总的计算次数（即调用次即可，那么总的计算次数（即调用MaxSum 函数的函数的次数）就是三角形中的数字总数，即次数）就是三角形中的数字总数，即1+2+3+N = N(N+1)/2。n 如何存放计算出来的如何存放计算出来的MaxSum（r, j）值呢？显然，用一个二）值呢？显然，用一个二维数组维数组aMaxSumNN就能解决。就能解决。aMaxSumrj就存放就存放MaxSum(r, j)的计算
30、结果。下次再需要的计算结果。下次再需要MaxSum(r, j)的值时，的值时，不必再调用不必再调用MaxSum 函数，只需直接取函数，只需直接取aMaxSumrj的值即的值即可。可。价澡植朵签札滴个伤末渊涝悄阅慧关谭引漆赞席絮纸屠舒选腹侄嘎坟宏利第十三周递归与动态规划二第十三周递归与动态规划二214、参考程序参考程序 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(
31、 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; return aMaxSumr+1j+1 + Drj;铱霍鹊靳硼昏盒呛首陶隙渴惠纬睦竣宛陛憋褪旷侣殖帚析这柴钝诊躯炉脸第十三周递归与动态规划二第十三周递归与动态规
32、划二224、参考程序参考程序 IIint main(void) int m; scanf(%d, & N); /将将 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, & Dij); printf(%d, MaxSum(1, 1); return 0;禄吧满鬼押遏危锚帅蕾酷阵嗜坛硅锥潞俞兑诡尸鸯嘶姻拘慌皖虚疆违功迁第十三周递归
33、与动态规划二第十三周递归与动态规划二23程序程序II分析分析 这种将一个问题分解为子问题递归求解，并且将中间结果这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做保存以避免重复计算的办法，就叫做“动态规划动态规划”。动态规动态规划通常用来求最优解，能用动态规划解决的求最优解问题，划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。必须满足，最优解的每个局部解也都是最优的。以上题为例，以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路
34、径。字出发到达到底部的最佳路径。实际上，递归的思想在编程时未必要实现为递归函数。在上实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：面的例子里，有递推公式：因此，不需要写递归函数，从因此，不需要写递归函数，从aMaxSumN-1这一行元素这一行元素开始向上逐行递推，就能求得开始向上逐行递推，就能求得aMaxSum11的值了。的值了。击牢店园奄栈旬放齐焰觅妮卢荆纬琴砰砰夷现谦片友粘置盟葛青狸啊留寇第十三周递归与动态规划二第十三周递归与动态规划二245、参考程序 IIIint DMAX_NUM + 10MAX_NUM + 10;int N;int aMaxSumMAX_
35、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; else aMaxSumi-1j = aMaxSumij+1 + Di-1j; printf(%d, aMaxSum11); return 0;思考题思考题：上面的几个程序
36、：上面的几个程序只算出了最佳路径的数字只算出了最佳路径的数字之和。如果要求输出最佳之和。如果要求输出最佳路径上的每个数字，该怎路径上的每个数字，该怎么办？么办？袄艇惹挪昂赌迸晰钒睬态库佛鲸鹃滇网丛务窃呀龙说桑宝泄悬挣芝予菜蟹第十三周递归与动态规划二第十三周递归与动态规划二25动态规划解题的一般思路动态规划解题的一般思路 n 许多求最优解的问题可以用动态规划来解决。许多求最优解的问题可以用动态规划来解决。n 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导首先要把原问题分解为若干个子问题。注意单纯的递归往往会导致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就致子问题被重复计算，
37、用动态规划的方法，子问题的解一旦求出就要被保存，所以每个子问题只需求解一次。要被保存，所以每个子问题只需求解一次。 n 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的从原来的n 变成了变成了n-1，或从原来的，或从原来的nm 变成了变成了n(m-1) 等等等。等。n 找到子问题，就意味着找到了将整个问题逐渐分解的办法。找到子问题，就意味着找到了将整个问题逐渐分解的办法。n 分解下去，直到最底层规模最小的的子问题可以一目了然地看出分解下去，直到最底层规模最小的的子问题可以一目了然地看出解。解。n 每一层子问题的解决，会导致
38、上一层子问题的解决，逐层向上，每一层子问题的解决，会导致上一层子问题的解决，逐层向上，就会导致最终整个问题的解决。就会导致最终整个问题的解决。n 如果从最底层的子问题开始，自底向上地推导出一个个子问题的如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程的时候就不需要写递归函数。解，那么编程的时候就不需要写递归函数。低瑟坏房且破耸胞咐苯蒸溢俺清猪媚贸械朴晚酉始酪寡冰棋姥环弱敞人鹃第十三周递归与动态规划二第十三周递归与动态规划二26动态规划解题的一般思路动态规划解题的一般思路 n 用动态规划解题时，将和子问题相关的各个变量的一组取值，用动态规划解题时，将和子问题相关的各个变量的一
39、组取值，称之为一个称之为一个“状态状态”。一个。一个“状态状态”对应于一个或多个子问题，对应于一个或多个子问题，所谓某个所谓某个“状态状态”下的下的“值值”，就是这个，就是这个“状态状态”所对应的子所对应的子问题的解。问题的解。n 比如数字三角形，子问题就是比如数字三角形，子问题就是“从位于从位于(r，j)数字开始，到数字开始，到底边路径的最大和底边路径的最大和”。这个子问题和两个变量。这个子问题和两个变量r 和和j 相关，那相关，那么一个么一个“状态状态”，就是，就是r, j 的一组取值，即每个数字的位置就的一组取值，即每个数字的位置就是一个是一个“状态状态”。该。该“状态状态”所对应的所对
40、应的“值值”，就是从该位置，就是从该位置的数字开始，到底边的最佳路径上的数字之和。的数字开始，到底边的最佳路径上的数字之和。n 定义出什么是定义出什么是“状态状态”，以及在该，以及在该 “状态状态”下的下的“值值”后，后，就要找出不同的状态之间如何迁移就要找出不同的状态之间如何迁移即如何从一个或多个即如何从一个或多个“值值”已知的已知的 “状态状态”，求出另一个，求出另一个“状态状态”的的“值值”。状态。状态的迁移可以用递推公式表示，此递推公式也可被称作的迁移可以用递推公式表示，此递推公式也可被称作“状态转状态转移方程移方程”。背酝入苦欠浪钢轿吱耍鸿贮宰揉吝飞歹捍如痈企蛋筹饱袍从瘟暮根皮蜂锅第
41、十三周递归与动态规划二第十三周递归与动态规划二27动态规划解题的一般思路动态规划解题的一般思路 n用用动动态态规规划划解解题题，如如何何寻寻找找“子子问问题题”，定定义义“状状态态”，“状状态态转转移移方方程程”是是什什么么样样的的，并并没没有有一一定定之之规规，需需要要具具体体问问题题具体分析，题目做多了就会有感觉。具体分析，题目做多了就会有感觉。n甚甚至至，对对于于同同一一个个问问题题，分分解解成成子子问问题题的的办办法法可可能能不不止止一一种种，因因而而“状状态态”也也可可以以有有不不同同的的定定义义方方法法。不不同同的的“状状态态”定定义义方法可能会导致时间、空间效率上的区别。方法可能
42、会导致时间、空间效率上的区别。炳骄籍佣肥屡伸缨浦殿戚赎魁总否诧纱穿匿颓腕究耀扇残蜜侨科皆跃洞部第十三周递归与动态规划二第十三周递归与动态规划二28最长上升子序列最长上升子序列 1、问题描述、问题描述 一一个个数数的的序序列列bi，当当b1 b2 . bS 的的时时候候，我我们们称称这这个个序序列列是是上上升升的的。对对于于给给定定的的一一个个序序列列(a1, a2, ., aN)，我我们们可可以以得得到到一一些些上上升升的的子子序序列列(ai1, ai2, ., aiK)，这这里里1 = i1 i2 . iK = N。比比如如，对对于于序序列列(1, 7, 3, 5, 9, 4, 8)，有有它
43、它的的一一些些上上升升子子序序列列，如如(1, 7), (3, 4, 8)等等等等。这这些些子子序序列列中中最长的长度是最长的长度是4，比如子序列，比如子序列(1, 3, 5, 8).你你的的任任务务，就就是是对对于于给给定定的的序序列列，求求出出最最长长上上升升子子序序列的长度。列的长度。寇腿穗祁唁尺涣曰秸冗臼沟唁晰腥阂眩斩径秃辙向姐逮邵重饶柱恳躯辟捌第十三周递归与动态规划二第十三周递归与动态规划二29问题描述问题描述输入数据输入数据输入的第一行是序列的长度输入的第一行是序列的长度N (1 = N = 1000)。第二行。第二行给出序列中的给出序列中的N 个整数，这些整数的取值范围都在个整数
44、，这些整数的取值范围都在0 到到10000。输出要求输出要求最长上升子序列的长度。最长上升子序列的长度。输入样例输入样例71 7 3 5 9 4 8输出样例输出样例4略压酷垣牙啼赡蝇辱疾罗运场扬砷沽膳离荫曲舔魏史虎伤竞伙猪扰菲穴娄第十三周递归与动态规划二第十三周递归与动态规划二302、解题思路解题思路 n 如何把这个问题分解成子问题呢？经过分析，发现如何把这个问题分解成子问题呢？经过分析，发现 “求以求以ak（k=1, 2, 3N）为终点的最长上升子序列的长度）为终点的最长上升子序列的长度”是个是个好的子问题好的子问题这里把一个上升子序列中最右边的那个数，称这里把一个上升子序列中最右边的那个数
45、，称为该子序列的为该子序列的“终点终点”。虽然这个子问题和原问题形式上并不。虽然这个子问题和原问题形式上并不完全一样，但是只要这完全一样，但是只要这N 个子问题都解决了，那么这个子问题都解决了，那么这N 个子问个子问题的解中，最大的那个就是整个问题的解。题的解中，最大的那个就是整个问题的解。n 由上所述的子问题只和一个变量相关，就是数字的位置。因由上所述的子问题只和一个变量相关，就是数字的位置。因此序列中数的位置此序列中数的位置k 就是就是“状态状态”，而状态，而状态 k 对应的对应的“值值”，就是以就是以ak 做为做为“终点终点”的最长上升子序列的长度。这个问题的最长上升子序列的长度。这个问
46、题的状态一共有的状态一共有N 个。状态定义出来后，转移方程就不难想了。个。状态定义出来后，转移方程就不难想了。 茨彻专虹堵秘愚巷填烦利岔霖段食窜楞痘钉闭岗厨久喳橇刷雍僧脊信蚤滁第十三周递归与动态规划二第十三周递归与动态规划二312、解题思路解题思路 n假假定定MaxLen (k)表表示示以以ak 做做为为“终终点点”的的最最长长上上升升子子序序列列的长度，那么：的长度，那么：nMaxLen (1) = 1nMaxLen (k) = Max MaxLen (i)：1i k 且且 ai ak 且且 k1 + 1n这这个个状状态态转转移移方方程程的的意意思思就就是是，MaxLen(k)的的值值，就就
47、是是在在ak 左左边边，“终终点点”数数值值小小于于ak，且且长长度度最最大大的的那那个个上上升升子子序序列列的的长长度度再再加加1。因因为为ak 左左边边任任何何“终终点点”小小于于ak 的的子子序序列列，加加上上ak 后就能形成一个更长的上升子序列。后就能形成一个更长的上升子序列。n实实际际实实现现的的时时候候，可可以以不不必必编编写写递递归归函函数数，因因为为从从 MaxLen(1)就就 能能 推推 算算 出出 MaxLen(2)， 有有 了了 MaxLen(1)和和MaxLen(2)就能推算出就能推算出MaxLen(3)桂凡眯肃宪诅椰搂舜涌莫苇玻瞩篙墒努搜峰陋盛阜获撼墟蹄隅庐偿刺抨庐第
48、十三周递归与动态规划二第十三周递归与动态规划二323、参考程序参考程序int bMAX_N + 10;int aMaxLenMAX_N + 10;int main(void) int i, j, N; scanf(%d, & N); for( i = 1;i = N;i + ) scanf(%d, & bi); aMaxLen1 = 1;籽烘六御碗氏有掖伍惩狰脐试拉取企僻瑰且误议砖滁鹤扶惕厅抚姿初蔫藉第十三周递归与动态规划二第十三周递归与动态规划二333、参考程序 for( i = 2; i = N; i + ) /求以第求以第i 个数为终点的最长上升子序列的长度个数为终点的最长上升子序列的长
49、度 int nTmp = 0; /记录第记录第i 个数左边子序列最大长度个数左边子序列最大长度 for( j = 1; j bj ) if( nTmp aMaxLenj ) nTmp = aMaxLenj; aMaxLeni = nTmp + 1; int nMax = -1; for( i = 1;i = N;i + ) if( nMax aMaxLeni) nMax = aMaxLeni; printf(%dn, nMax); return 0;思考题：改进此程序，使之思考题：改进此程序，使之能够输出最长上升子序列能够输出最长上升子序列 龟灶含鹊按劝痔酸伙这混坟也瞳榴京凉壹采姬幌拖渐匆掀揉熊辽壤吱垦伟第十三周递归与动态规划二第十三周递归与动态规划二34
