《程序设计-动态规划【】课件.ppt》由会员分享，可在线阅读，更多相关《程序设计-动态规划【】课件.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八讲动态规划例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)11001010int fn+1;f1=f2=1;for(int i=3;i=n;i+)fi=fi-1+fi-2;cout fn endl;为了除去冗余计算,可以从已知条件开始计算,并记录计算过程中的中间结果。输入格式入格式:第一行是三角形
2、行数,下面是三角形。57388 1 02 7 4 4 4 5 2 6 5 输出出:要求输出最大和。解题思路解题思路D(r,j):表示第r行第 j 个数字;MaxSum(r,j):表示从D(r,j)到底边的各条路径中,数字之和最大的那条路径的数字之和;本题目标是求:MaxSum(0,0)。从某个D(r,j)出发,下一步只能走D(r+1,j)或者D(r+1,j+1)。所以,对于N行的三角形,可以得到递推公式:if(r=N-1)MaxSum(r,j)=D(N-1,j);else MaxSum(r,j)=Max MaxSum(r1,j),MaxSum(r+1,j+1)+D(r,j);#include#
3、define MAX 101 int triangleMAXMAX;int n;int longestPath(int i,int j);void main()int i,j;cin n;for(i=0;i n;i+)for(j=0;j triangleij;cout longestPath(0,0)endl;数字三角形的递归程序数字三角形的递归程序为什么超什么超时？因为重复计算太多！7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 如果采用递规的方法,深度遍历每条路径,存在大量重复计算。则时间复杂度为 2n,对于 n=100,肯定超时。从下往上计算,对于每一点,需要保留从底边上来到
4、此点的路径中和最大的路径的和。递推公式:MaxSum(r,j)=Max MaxSum(r1,j),MaxSum(r+1,j+1)+D(r,j);7 3 8 8 1 0 2 7 4 4 4 5 2 6 5#define MAX_NUM 100int DMAX_NUM+10MAX_NUM+10;int N;int aMaxSumMAX_NUM+10MAX_NUM+10;main()int i,j;scanf(%d,&N);for(i=0;i N;i+)for(j=0;j i;j+)scanf(%d,&Dij);for(j=0;j 0;i-)for(j=0;j aMaxSumij+1)aMaxSum
5、i-1j=aMaxSumij+Di-1j;else aMaxSumi-1j=aMaxSumij+1+Di-1j;printf(%d,aMaxSum00);#define MAX_NUM 100int DMAX_NUM+10MAX_NUM+10;int N;int aMaxSumMAX_NUM+10;main()int i,j;scanf(%d,&N);for(i=0;i N;i+)for(j=0;j i;j+)scanf(%d,&Dij);for(j=0;j 0;i-)for(j=0;j aMaxSumj+1)aMaxSumj=aMaxSumj+Di-1j;else aMaxSumj=aMax
6、Sumj+1+Di-1j;printf(%d,aMaxSum1);7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 递归到动态规化的一般转化方法原来递归函数有几个参数,就定义一个几维的数组。数组的下标是递归函数参数的取值范围。数组元素的值是递归函数的返回值。这样就可以从边界开始,逐步填充数组,相当于计算递归函数值的逆过程。输入数据输入数据输入的第一行是序列的长度N(1=N=1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。输出要求输出要求最长上升子序列的长度。输入样例输入样例71 7 3 5 9 4 8输出样例输出样例4问题分析已知序列:a1,a2,a3,
7、aN,求nMax(该序列最长上升子序列长度)考虑最长上升子序列中的第一个数:是ak吗?如果知道以ak为“起始”的最长子序列的长度呢？设MaxLen(k):表示以ak做为“起点”的最长上升子序列的长度。则:nMax =max MaxLen(k):k=1,2,N 解题思路1.1.找子问题找子问题:经过分析,发现“求以a1(k=1,2,3N)为起点的最长上升子序列的长度”是个好的子问题这里把一个上升子序列中最左边的那个数,称为该子序列的“起点”。虽然这个子问题和原问题形式上并不完全一样,但是只要这N个子问题都解决了,那么这N个子问题的解中,最大的那个就是整个问题的解。2.2.确定状态确定状态:上所述
8、的子问题只和一个变量相关,就是数字的位置。因此序列中数的位置k 就是“状态”,而状态 k 对应的“值”,就是以ak做为“起点”的最长上升子序列的长度。这个问题的状态一共有N个。3.3.找出递推关系找出递推关系:假定MaxLen(k)表示以ak做为“起点”的最长上升子序列的长度,那么:MaxLen(N)=1;MaxLen(N)=1;MaxLen(k)=max MaxLen(i):k i N MaxLen(k)=max MaxLen(i):k i N 且且 a ak kaai i+1,+1,当当 1k=N1k=N时。时。这个状态转移方程的意思就是,MaxLen(k)的值,就是在ak右边,“起点”数
9、值大于ak,且长度最大的那个上升子序列的长度再加1。因为ak右边任何“起点”小于ak的子序列,加上ak后就能形成一个更长的上升子序列。实际实现的时候,可以不必编写递归函数,因为从 MaxLen(N)就能推算出MaxLen(N-1),有了MaxLen(N)和MaxLen(N-1)就能推算出MaxLen(N-2)for(i=N-1;i=1;i+)/每次求以第i个数为起点的 /最长上升子序列的长度int nTmp=0;/记录满足条件的,第i个数右边的上升 /子序列的最大长度for(int j=i+1;j =N;j+)/察看以第j个 数为 /起点的最长上升子序列if(bi bj)if(nTmp aMa
10、xLenj)nTmp=aMaxLenj;aMaxLeni =nTmp+1;int nMax=-1;for(i=1;i=N;i+)if(nMax aMaxLeni)nMax=aMaxLeni;printf(%dn,nMax);例题:Poj 1458 最长公共子序列给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到,而且每个字符的先后顺序和原串中的先后顺序一致。最长公共子序列输入样例输入样例abcfbc abfcab programming contestabcd mnp 输出样例输出样例420 l输入两个子串s1,s2。l设MaxLen(i,j)表示:s
11、1的左边i个字符形成的子串,与s2左边的j个字符形成的子串的最长公共子序列的长度。l假定 len1=strlen(s1),len2=strlen(s2),那么题目就是要求:MaxLen(len1,len2)最长公共子序列递推公式递推公式: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);显然:MaxLen(n,0)=0 (n=0len1)MaxLen(0,n)=0 (n=0len2)最长公共子序列for(i=1;i=nLength1;i+)for(j=1;j
12、nLen2)anMaxLenij=nLen1;elseanMaxLenij=nLen2;cout anMaxLennLength1nLength2 endl;活学活用掌握递归和动态规划的思想,解决问题时灵活应用。例题例题:POJ 1661POJ 1661 Help Jimmy Help JimmyHelp Jimmy 是在下图所示的场景上完成的游戏:场景中包括多个长度和高度各不相同的平台。地面是最低的平台,高度为零,长度无限。Jimmy老鼠在时刻0从高于所有平台的某处开始下落,它的下落速度始终为1米/秒。当Jimmy落到某个平台上时,游戏者选择让它向左还是向右跑,它跑动的速度也是1米/秒。当J
13、immy跑到平台的边缘时,开始继续下落。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=20000,0 Hi Y=20000(
14、i=1.N)。所有坐标的单位都是米。Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘,被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy一定能安全到达地面。输出要求输出要求对输入的每组测试数据,输出一个整数,Jimmy到地面时可能的最早时间。输入样例输入样例13 8 17 200 10 80 10 134 14 3输出样例输出样例23Jimmy跳到一块板上后,可以有两种选择,向左走,或向右走。走到左端和走到右端所需的时间,是很容易算的。如果我们能知道,以左端为起点到达地面的最短时间,和以右端为起点到达地面的最短时间,那么向左走还是向右走,就很容选择了。
15、解题思路解题思路因此,整个问题就被分解成两个子问题,即Jimmy所在位置下方第一块板左端为起点到地面的最短时间,和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。将板子从上到下从1开始进行无重复的编号(越高的板子编号越小,高度相同的几块板子,哪块编号在前无所谓),那么,和上面两个子问题相关的变量就只有板子的编号。解题思路解题思路不妨认为Jimmy开始的位置是一个编号为0,长度为0的板子,假设LeftMinTime(k)表示从k号板子左端到地面的最短时间,RightMinTime(k)表示从k号板子右端到地面的最短时间,那么,求板子k左端点到地面的最短时间的方法如下:if(
16、板子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号板子的落脚点走到m
17、号板子左端点的时间,Rx(m)-Lx(k)就是从m号板子的落脚点走到右端点所需的时间。求RightMinTime(k)的过程类似。不妨认为Jimmy开始的位置是一个编号为0,长度为0的板子,那么整个问题就是要求LeftMinTime(0)。输入数据中,板子并没有按高度排序,所以程序中一定要首先将板子排序。有一个由1.9组成的数字串。问如果将m个加号加号插入到这个数字串中,在各种可能形成的表达式中,值最小的那个表达式的值是多少？最佳加法表达式最佳加法表达式考虑最后一个加号的位置。假定数字串长度是n。添完加号后,表达式的最后一个加号添加在第 i 个数字后面,那么整个表达式的最小值,就等于在前 i 个数字中插入 m 1个加号所能形成的最小值,加上第 i+1到第 n 个数字所组成的数的值。设V(m,n)表示在n个数字中插入m个加号所能形成的表达式最小值,那么:if(m=0)V(m,n)=Num(1,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-1);Num(k,j)表示从第k个字符到第j个字符所组成的数,数字编号从1开始算。作业ai 1088:滑雪ai 2774:木材加工