动态规划1--最长公共子序列

一、动态规划

经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并
综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。

为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就
是动态规划法所采用的基本方法。

二、心得

递推公式的推导

递推公式的证明方法

代码的写法：把递推公式直接写进代码即可

 

三、题目

给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。

Sample Input：样例输入

abcfbc abfcab

programming contest

abcd mnp

Sample Output：样例输出

4
2
0

 

四、分析

 

 

2、证明
S1[i-1]!= s2[j-1]时，MaxLen(S1,S2)不会比MaxLen(S1,S2j-1)
和MaxLen(S1i-1,S2)两者之中任何一个小，也不会比两者都大。
（1）不比任何一个小：MaxLen(S1,S2)字符串长于后两者
（2）也不会比两者都大：反证法，假设比两者都大：

若MaxLen(S1,S2)比MaxLen(S1,S2j-1)大，说明S2(j)这个字符与S1中的字符相等，并且S2(j)和这个相等的字符是最长公共子序列的最后一个。

若MaxLen(S1,S2)比MaxLen(S1i-1,S2)大，说明S1(i)这个字符与S2中的字符相等，并且S1(i)和这个相等的字符是最长公共子序列的最后一个。

上面两种情况都是最长公共子序列的最后一个，而这个最长公共子序列是MaxLen(S1,S2)的最长公共子序列，所以最后一个要相等。

那会得出S1[i]== s2[j]的结论，与假设冲突。

 

五、代码及结果

1 /* 2 最长公共子序列 3 1、递推公式： 4 （分最后一个相同和最后一个不同来分析） 5 当i或j等于0，MaxLen(i,j)==0; 6 当s1和s2的最后一个字符相同时，MaxLen(i,j)=MaxLen(i-1,j-1)+1; 7 当s1和s2的最后一个字符不同时，MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) ); 8 2、证明 9 S1[i-1]!= s2[j-1]时，MaxLen(S1,S2)不会比MaxLen(S1,S2j-1) 10 和MaxLen(S1i-1,S2)两者之中任何一个小，也不会比两者都大。 11 （1）不比任何一个小：MaxLen(S1,S2)字符串长于后两者 12 （2）也不会比两者都大：反证法，假设比两者都大，那会得出S1[i-1]== s2[j-1]的结论，与假设冲突 13 3、代码 14 直接写递推公式就好了 15 */ 16 /* 17 错误一：结果不对 18 for(j=1;j<=length2;j++)，漏了等号，所以都没执行到这来，所以结果不对 19 */ 20 #include <iostream> 21 #include <cstring> 22 using namespace std; 23 char sz1[1000];//字符数组1 24 char sz2[1000];//字符数组2 25 int maxLen[1000][1000]; 26 //MaxLen(i,j)表示s1的左边i个字符形成的子串， 27 //与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0开始算） 28 int main(){ 29 freopen("in.txt","r",stdin); 30 while(cin>>sz1>>sz2){ 31 int length1=strlen(sz1);//求字符数组1的长度 32 int length2=strlen(sz2);//求字符数组2的长度 33 int nTmp; 34 int i,j; 35 //初始化边界情况 36 for(i=0;i<=length1;i++) 37 maxLen[i][0]=0; 38 for(j=0;j<=length2;j++) 39 maxLen[0][j]=0; 40 //动态规划求解最长公共子序列 41 for(i=1;i<=length1;i++){ 42 for(j=1;j<=length2;j++){ 43 if(sz1[i-1]==sz2[j-1]){//字符数组从0开始存数据的 44 //当s1和s2的最后一个字符相同时，MaxLen(i,j)=MaxLen(i-1,j-1)+1; 45 maxLen[i][j]=maxLen[i-1][j-1]+1; 46 } 47 else{ 48 //当s1和s2的最后一个字符不同时，MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) ); 49 maxLen[i][j]=max(maxLen[i][j-1],maxLen[i-1][j]); 50 } 51 } 52 53 } 54 /* 55 for(i=1;i<=length1;i++){ 56 for(j=1;j<=length2;j++){ 57 cout<<maxLen[i][j]<<" "; 58 } 59 cout<<endl; 60 } 61 */ 62 //cout<<length1<<" "<<length2<<endl; 63 cout<<maxLen[length1][length2]<<endl; 64 } 65 return 0; 66 }

 

总结

以上是生活随笔为你收集整理的动态规划1--最长公共子序列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。