《数学动态规划》课件.ppt

1、z递归：z（1）将原问题分解为更小规模的同类问题z（2）结束条件z#include stdio.hzint factorial(int n)zzif(ng(f(x-x)每个f(x-x)只计算一次。|例：POJ 2753 Fibonacci数列|1，1，f(n-1)+f(n-2),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冗余计算冗余计算|例：POJ 2753 Fibonacci数列计算过程中存在冗

2、余计算，为了出去冗余计算可以从已知条件开始计算，并记录计算过程中的中间结果。f(1)1|例：POJ 2753 Fibonacci数列int fn+1;f1=f2=1;int I;for(i=3;i=n;i+)fi=fi-1+fi-2;cout fn=MaxSum(row+1,col+1)|return MaxSum(row+1,col)+elemrowcol;|else|return MaxSum(row+1,col+1)+elemrowcol;|int main(int argc,char*argv)|scanf(%d,&n);|int i,j;|for(i=1;i=n;i+)|for(j=

3、1;j=MaxSum(row+1,col+1)|return MaxSum(row+1,col)+elemrowcol;|else|return MaxSum(row+1,col+1)+elemrowcol;|int main(int argc,char*argv)|scanf(%d,&n);|memset(aMaxSum,-1,sizeof(aMaxSum);|int i,j;|for(i=1;i=n;i+)|for(j=1;j=i;j+)|scanf(%d,&elemij);|printf(%dn,MaxSum(1,1);|getchar();|return 0;|Sets buffers

4、 to a specified character.|void*memset(void*dest,int c,size_t count);|dest|Pointer to destination|c|Character to set|count|Number of characters|动态规划：将一个问题分解为子问题递归求解，将中间结果保存以避免重复计算的方法。|求最优解|一切子问题也是最优的|递归 递推|aMaxSumij=|elemij i=n|max(aMaxSum(i+1,j),aMaxSum(i+1,j)in|算法二：动态规划从下往上逐层计算|#include memory.h|i

5、nt n;|int elem101101;|int aMaxSum101101;|int main(int argc,char*argv)|scanf(%d,&n);|memset(aMaxSum,-1,sizeof(aMaxSum);|int row,col;|for(row=1;row=n;row+)|for(col=1;col=1;row-)|for(col=1;col=aMaxSumrow+1col+1)|aMaxSumrowcol=aMaxSumrow+1col+elemrowcol;|else|aMaxSumrowcol=aMaxSumrow+1col+1+elemrowcol;|

6、printf(%dn,aMaxSum11);|getchar();|return 0;|解题步骤：|（1）问题分解为子问题|越来越简单|最终直接有解|（2）状态：子问题对应的变量|的值及结果|（3）状态迁移|从已知状态推导未知状态|aMaxSumij=|elemij i=n|max(aMaxSum(i+1,j),aMaxSum(i+1,j)iMaxStr(str1,len1,str2,len2-1)|return MaxStr(str1,len1-1,str2,len2);|else|return MaxStr(str1,len1,str2,len2-1);|int main(int argc

7、,char*argv)|gets(str1);|gets(str2);|printf(%dn,MaxStr(str1,strlen(str1),str2,strlen(str2);|getchar();|return 0;|递归过程如下：|abcfbc abfcab|abcfb abfcab|abcf abfca|abc abfca|ab abfca|a abfca|abfca|算法二：动态规划从str1和str2的第一个字符开始考虑；int comLenMAXMAX;用一个二维数组记录str1的前i个字符与str2中的前j个字符的最大公共子串长度（状态）|设立初值：comLen 00MAX=

8、0;comLen 0MAX0=0;表示两个字符串中有一个没有参与比较时，最大公共子串长度为|递推：if(stri=strj)comLen ij=1+comLen i-1j-1;else comLenij=max(comLeni-1j,comLenij-1);|#include stdio.h|#include memory.h|#include string.h|#define MAX 100|char str1MAX;|char str2MAX;|int comMAXMAX;|int main(int argc,char*argv)|int i,j;|while(1)|gets(str1);

9、if(str10=0)break;|gets(str2);|int len1=strlen(str1);|int len2=strlen(str2);|for(i=0;iMAX;i+)|for(j=0;jMAX;j+)|comij=0;|for(i=1;i=len1;i+)|for(j=1;jcomij-1)comij=comi-1j;|else comij=comij-1;|/else|/for|printf(%dn,comlen1len2);|/while|getchar();|return 0;|void main()|char ch;|while(ch=getchar()!=EOF)|

10、putchar(ch);|CTRL+Z|例11POJ 2755神奇口袋前面介绍了用递归的方法解此题，核心思想是逐一枚举每个数的使用情况，用或不用，这里可以用动态规划的方法实现这一想法即有n个数，则用1到2n所表示的二进制数来枚举所有这些数的组合情况，例如：n=3，则表示用第和第个数，不用第个数，检验有多少种组合的和是，就得到了问题的解#include void main()int n,i,j,k,count40=0;cin n;int numbers21;for(i=0;i numbersi;for(i=1;i10;j=1,k-)if(j&1)sum+=numbersk;if(sum=40)c

11、ount40+;cout count40 endl;枚举组合太多，超时，如果n增大，更是不可想象|算法三，因为要凑出，可以考虑记录所有能够凑出的组合的数目，|定义数组 int sum41；sumi表示能够凑出和为i的次数|考虑只用a1能凑出a1一次，用a2能够凑出a2一次，a1+a2一次，|用a3能够凑出a3一次，它与前面的所有能够凑出的数相加得到的数各一次|依次类推，使用所有的数，并计算能够得到的和的可能及每种和的次数#include#define MAX 41void main()int n,i,j,input;int sumMAX;for(i=0;i n;for(i=0;i input;

12、for(j=40;j=1;j-)if(sumj0&j+input=40)sumj+input+=sumj;suminput+;cout sum40 endl;|例12POJ 平板上色问题|问题描述：一个平板被一组大小不等的长方形覆盖，现在需要为每个长方形上一种颜色。每个长方形需要上的颜色是预先确定的。每种画笔上一种颜色。但为了避免画笔将涂料滴到已经上好色的、且颜色不同的长方形上，在对一个长方形A上色前，要求：位于A正上方的其它长方形都已上好色。每取一次画笔，可以为多个长方形上色。请编写一个程序，计算为了完成一个平板的全部上色，最少需要取多少次画笔。算法一：一步枚举递归枚举第一次使用的颜色，将能

13、涂色的矩形x个涂色，则剩下的矩形数目减少x个，变成更小规模的同类问题，递归下去源程序最坏情况下,枚举次数为15*1414,会超过秒，改用递归的方法算法二：动态规划用枚举矩形被刷与不刷的状态，在每种状态下，枚举最后一次刷的矩形下的最小换笔次数，即enumerateij;i取值范围是，表示每个举行刷与未刷的状态，j取值范围是，表示当前状态下最后一次刷的矩形，enumerateij表示某种状态下的换笔最小次数；对于*15种状态，逐一枚举下一次涂色的矩形，如果该矩形颜色与最后一次涂色的矩形相同，则原状态新矩形的最小取笔次数等于原状态取笔次数，否则原状态新矩形的最小取笔次数等于原状态取笔次数。本题的解就是找出在状态 下，即所有矩形均被涂色后，最后涂色的个矩形中哪个用的取笔次数最小。例如：源程序作业：1、Fibonacci数列的递归式动态规划算法。2、最长上升子序列 一个数的序列bi，当b1 b2 bs的时候，这个序列是上升的。对于给定的一个序列(a1，a2，aN),可以得到一些上升的子序列(ai1，ai2,，aiK),这里1i1i2iK N。比如，对于序列(1，7，3，5，9，4，8),有它的一些上升子序列，如(1，7),(3，4，8)等。这些子序列中最长的长度是4，比如子序列（1，3，5，8）。你的任务就是对于给定的序列，求出最长上升子序列的长度。