程序设计实习(II)19-动态规划课件.ppt

《程序设计实习(II)19-动态规划课件.ppt》由会员分享，可在线阅读，更多相关《程序设计实习(II)19-动态规划课件.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、程序设计实习程序设计实习动态规划树形递归存在冗余计算树形递归存在冗余计算l例1：POJ 2753 Fibonacci数列求 Fibonacci数列的第n项int f(int n)if(n=0|n=1)return n;return f(n-1)+f(n-2);f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010冗余计算冗余计算计算过程中存在冗余计算，为了除去冗余计算可以从已知条件开始计算，并记录计算过程中的中间结果。树形递归存在冗余计算树形递归存在冗余计算去除冗余：int fn+1;f1=f2=1;int I;

2、for(i=3;i=n;i+)fi=fi-1+fi-2;cout fn 动态规划输入格式：5/三角形行数。下面是三角形73 88 1 02 7 4 4 4 5 2 6 5 要求输出最大和解题思路：以D(r,j)表示第r行第 j 个数字，以MaxSum(r,j)代表从第 r 行的第 j 个数字到底边的各条路径中，数字之和最大的那条路径的数字之和，则本题是要求 MaxSum(0,0)。（假设行编号和一行内数字编号都从0开始)。典型的动态规划问题。从某个D(r,j)出发，显然下一步只能走D(r+1,j)或者D(r+1,j+1)，所以，对于N行的三角形：if(r=N-1)MaxSum(r,j)=D(N

3、-1,j)else MaxSum(r,j)=Max(MaxSum(r1,j),MaxSum(r+1,j+1)+D(r,j),#include#include#define MAX 101#define MAX 101 int triangleMAXMAX;int triangleMAXMAX;int n;int n;int longestPath(int i,int j);int longestPath(int i,int j);Int main()Int main()int i,j;int i,j;cin n;cin n;for(i=0;in;i+)for(j=0;j=i;j+)for(i=

4、0;in;i+)for(j=0;j triangleij;cin triangleij;cout longestPath(0,0)endl;cout longestPath(0,0)endl;数字三角形的递归程序：为什么超时？为什么超时？l回答：重复计算 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 如果采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为 2n,对于 n=100 行，肯定超时。改进思想：从下往上计算，对于每一点，只需要保留从下面来的路径中和最大的路径的和即可。因为在它上面的点只关心到达它的最大路径和，不关心它从那条路经上来的。解法1：如果每算出一个

5、MaxSum(r,j)就保存起来，则可以用o(n2)时间完成计算。因为三角形的数字总数是 n(n+1)/2此时需要的存储空间是：int D100100;/用于存储三角形中的数字 int aMaxSum 100100;/用于存储每个MaxSum(r,j)解法2:没必要用二维Sum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组Sum100即可,即只要存储一行的MaxSum值就可以。比解法一改进之处在于节省空间，时间复杂度不变#define MAX_NUM 100int DMAX_NUM+10MAX_NUM+10;int N;int aMaxSumMAX_NUM+1

6、0;int main()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 aMaxSumj+1)aMaxSumj=aMaxSumj+Di-1j;else aMaxSumj=aMaxSumj+1+Di-1j;printf(%d,aMaxSum1);动规解题的一般思路动规解题的一般思路1.将原问题分解为子问题l把原问题分解为若干个子问题，子问题经常和原问题形式相似，有时甚至完全一样，只不过规模变小了l子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。动规解题的

7、一般思路动规解题的一般思路2.确定状态l在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题，所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。动规解题的一般思路动规解题的一般思路2.确定状态所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。在数字三角形的例子里，一共有N(N+1)/2个数字，所以这个问题的状态空间里一共就有N(N+1)/2个状态。在该问题里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。动规解题的一般思路动规解题

8、的一般思路2.确定状态用动态规划解题，经常碰到的情况是，K个整型变量能构成一个状态（如数字三角形中的行号和列号这两个变量构成“状态”）。如果这K个整型变量的取值范围分别是N1,N2,Nk，那么，我们就可以用一个K维的数组arrayN1 N2Nk来存储各个状态的“值”。这个“值”未必就是一个整数或浮点数，可能是需要一个结构才能表示的，那么array就可以是一个结构数组。一个“状态”下的“值”通常会是一个或多个子问题的解。动规解题的一般思路动规解题的一般思路3.确定状态转移方程定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移即如何从一个或多个“值”已知的“状态”，

9、求出另一个“状态”的“值”。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。数字三角形的状态转移方程输入数据输入的第一行是序列的长度N(1=N=1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。输出要求最长上升子序列的长度。输入样例71 7 3 5 9 4 8输出样例4解题思路解题思路1.1.找子问题找子问题经过分析，发现“求以ak（k=1,2,3N）为终点的最长上升子序列的长度”是个好的子问题这里把一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解

10、中，最大的那个就是整个问题的解。2.确定状态：上所述的子问题只和一个变量相关，就是数字的位置。因此序列中数的位置k 就是“状态”，而状态 k 对应的“值”，就是以ak做为“终点”的最长上升子序列的长度。这个问题的状态一共有N个。#include#include#define MAX_N 1000int bMAX_N+10;int aMaxLenMAX_N+10;main()int N;scanf(%d,&N);for(int i=1;i=N;i+)scanf(%d,&bi);aMaxLen1=1;for(i=2;i=N;i+)/每次求以第i个数为终点的最长上升子序列的长度int nTmp=0;

11、/记录满足条件的，第i个数左边的上升子序列的最大长度for(int 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);最长公共子序列Sample Inputabcfbc abfcab programming contestabcd mnp Sample Output420 输入两个子串s1,s2,设MaxLen(i,j)表示:s1的左边i个字符形成的子串，与s2左边的j个字符形成的子

12、串的最长公共子序列的长度MaxLen(i,j)就是本题的“状态”假定 len1=strlen(s1),len2=strlen(s2）那么题目就是要求MaxLen(len1,len2)最长公共子序列显然：MaxLen(n,0)=0 (n=0len1）MaxLen(0,n)=0 (n=0len2）递推公式：if(s1i-1=s2j-1)MaxLen(i,j)=MaxLen(i-1,j-1)+1;elseMaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j);最长公共子序列S1s1i-1S2s2j-1S1i-1S2j-1S1长度为 iS2长度为 jMaxLen(S1,

13、S2)不会比MaxLen(S1,S2j-1)和MaxLen(S1i-1,S2)都大，也不会比两者中任何一个小#include#include char sz11000;char sz21000;int anMaxLen10001000;main()while(cin sz1 sz2)int nLength1=strlen(sz1);int nLength2=strlen(sz2);int nTmp;int i,j;for(i=0;i=nLength1;i+)anMaxLeni0=0;for(j=0;j=nLength2;j+)anMaxLen0j=0;for(i=1;i=nLength1;i+

14、)for(j=1;j nLen2)anMaxLenij=nLen1;elseanMaxLenij=nLen2;cout anMaxLennLength1nLength2 endl;活学活用活学活用l掌握递归和动态规划的思想，解决问题时灵活应用例题：例题：POJ 1661POJ 1661 Help Jimmy Help JimmyHelp Jimmy 是在下图所示的场景上完成的游戏：场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑

15、，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。设计一个程序，计算Jimmy到地面时可能的最早时间。输入数据输入数据第一行是测试数据的组数t（0=t=20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1i，X2i和Hi。Hi表示平台的高度，X1i和X2i表示平台左右端点的横坐标。1=N=1000，-20000=X,X1i,X2i=200

16、00，0 Hi Y=20000（i=1.N）。所有坐标的单位都是米。Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy一定能安全到达地面。输出要求输出要求对输入的每组测试数据，输出一个整数，Jimmy到地面时可能的最早时间。输入样例输入样例13 8 17 200 10 80 10 134 14 3输出样例输出样例23Jimmy跳到一块板上后，可以有两种选择，向左走，或向右走。走到左端和走到右端所需的时间，是很容易算的。如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么

17、向左走还是向右走，就很容选择了。因此，整个问题就被分解成两个子问题，即Jimmy所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。将板子从上到下从1开始进行无重复的编号(越高的板子编号越小，高度相同的几块板子，哪块编号在前无所谓)，那么，和上面两个子问题相关的变量就只有板子的编号。解题思路：解题思路：不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子，假设LeftMinTime(k)表示从k号板子左端到地面的最短时间，RightMinTime(k)表示从k号板子右端到地面的最短时间，那么，求板子k左端点到地面的最短时

18、间的方法如下：if(板子k左端正下方没有别的板子)if(板子k的高度 h(k)大于Max)LeftMinTime(k)=;elseLeftMinTime(k)=h(k);else if(板子k左端正下方的板子编号是m)LeftMinTime(k)=h(k)-h(m)+Min(LeftMinTime(m)+Lx(k)-Lx(m),RightMinTime(m)+Rx(m)-Lx(k);上面，h(i)就代表i号板子的高度，Lx(i)就代表i号板子左端点的横坐标，Rx(i)就代表i号板子右端点的横坐标。那么 h(k)-h(m)当然就是从k号板子跳到m号板子所需要的时间，Lx(k)-Lx(m)就是从m

19、号板子的落脚点走到m号板子左端点的时间，Rx(m)-Lx(k)就是从m号板子的落脚点走到右端点所需的时间。求RightMinTime(k)的过程类似。不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子，那么整个问题就是要求LeftMinTime(0)。输入数据中，板子并没有按高度排序，所以程序中一定要首先将板子排序。有一个由有一个由1.9组成的数字串组成的数字串.问如果将问如果将m个加号个加号插入到这个数字串中插入到这个数字串中,在各种可能形成的表在各种可能形成的表达式中，值最小的那个表达式的值是多少达式中，值最小的那个表达式的值是多少最佳加法表达式最佳加法表达式 假定数字串长度是假定

20、数字串长度是n，添完加号后，添完加号后,表达表达式的最后一个加号添加在第式的最后一个加号添加在第 i 个数字后个数字后面，那么整个表达式的最小值，就等于面，那么整个表达式的最小值，就等于在前在前 i 个数字中插入个数字中插入 m 1个加号所能个加号所能形成的最小值，加上第形成的最小值，加上第 i+1到第到第 n 个数个数字所组成的数的值。字所组成的数的值。设V(m,n)表示在n个数字中插入m个加号所能形成的表达式最小值，那么：if m=0V(m,n)=n个数字构成的整数else if n m+1 V(m,n)=else V(m,n)=Min V(m-1,i)+Num(i+1,n)(i=m n-

21、1)Num(k,j)表示从第k个字符到第j个字符所组成的数数字编号从1开始算#include#include#include#include using namespace std;#define MAXN 15#define MAXM 15#define INFINITE 999999999/不考虑大整数加法 int anMinValueMAXMMAXN;/anMinValueij-1 表示把i个加号放到j个数字前面所能的到的最小值 /要求 anMinValuemn-1;int main()int m;string s;cin s m;int n=s.length();int i;for(i

22、=0;i n;i+)anMinValue0i=atoi(s.substr(0,i+1).c_str();for(i=1;i=m;i+)for(int j=0;j n;j+)/把i个加号放第j个数字前面 if(j i)anMinValuemj=INFINITE;else int nMin=INFINITE;for(int k=0;k=j-1;k+)/把i个加号里的最右边加号放在第k个字符后面 int nVal=0;for(int u=k+1;u=j;u+)nVal=nVal*10+s.c_str()u-0;nMin=min(nMin,anMinValuei-1k+nVal);anMinValueij=nMin;cout anMinValuemn-1;return 0;