动态规划II(含详细c语言代码).pptxVIP

第十课

动态规划(II)

综合实践考核

最长公共子序列

1、问题描述

我们称序列Z=z1,z2,...,zk是序列X=x1,x2,...,xm的子序列当且仅当存在严格上升的序列i1,i2,...,ik，使得对j=1,2,...,k,有xij=zj。比如Z=a,b,f,c是X=a,b,c,f,b,c的子序列。

现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。

输入数据

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。

问题描述

输出要求

对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。

输入样例

abcfbcabfcab

programmingcontest

abcdmnp

输出样例

4

2

0

2、解题思路

用字符数组s1、s2存放两个字符串，用s1[i]表示s1中的第i个字符，s2[j]表示s2中的第j个字符（字符编号从1开始），用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前j个字符构成的子串，MaxLen(i,j)表示s1i和s2j的最长公共子序列的长度，那么递推关系如下：

if(i==0||j==0)

MaxLen(i,j)=0//两个空串的最长公共子序列长度是0

elseif(s1[i]==s2[j])

MaxLen(i,j)=MaxLen(i-1,j-1)+1;

else

MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j));

显然本题目的“状态”就是s1中的位置i和s2中的位置j。

01

状态的数目是s1长度和s2长度的乘积。可以用一个二维数组来存储各个状态下的“值”。

03

“值”就是MaxLen(i,j)。

02

本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。

04

2、解题思路

3、参考程序

#includestdio.h

#includestring.h

#defineMAX_LEN1000

charsz1[MAX_LEN];

charsz2[MAX_LEN];

intaMaxLen[MAX_LEN][MAX_LEN];

intmain(void)

{

while(scanf(%s%s,sz1+1,sz2+1)0)

{

intnLength1=strlen(sz1+1);

intnLength2=strlen(sz2+1);

inti,j;

for(i=0;i=nLength1;i++)

aMaxLen[i][0]=0;

for(j=0;j=nLength2;j++)

aMaxLen[0][j]=0;

3、参考程序

for(i=1;i=nLength1;i++)

{

for(j=1;j=nLength2;j++)

{

if(sz1[i]==sz2[j])

aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;

else

{

intnLen1=aMaxLen[i][j-1];

intnLen2=aMaxLen[i-1][j];

if(nLen1nLen2)

aMaxLen[i][j]=nLen1;

else

aMaxLen[i][j]=nLen2;

}

}

}

printf(%d\n,aMaxLen[nLength1][nLeng