动态规划基础题目之最长公共子序列

动态规划基础题目之最长公共子序列

时间： 1ms        内存：128M

描述：

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

输入：

多组输入，一行输入两个字符串

输出：

输出最长公共子序列。

示例输入：

abcfbc         abfcab
programming    contest 
abcd           mnp

示例输出：

4
2
0

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
#include<string.h>
int main()
{
	char x[100],y[100];
	int l[100][100]={{0}},m,n,i,j;
	while(scanf("%s%s",x,y)!=EOF)
	{
		m=strlen(x);
		n=strlen(y);
		for(i=1;i<=m;++i)
		{
			for(j=1;j<=n;++j)
			{
				if(x[i-1]==y[j-1])
					l[i][j]=l[i-1][j-1]+1;
				else
					l[i][j]=((l[i-1][j]>l[i][j-1])?l[i-1][j]:l[i][j-1]);
			}
		}
		printf("%d\n",l[m][n]);
	}
	return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <cstring>
using namespace std;
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];
int main()
{
    while( cin >> sz1 >> sz2 )
    {
        int length1 = strlen( sz1);
        int length2 = strlen( sz2);
        int i,j;
        for( i = 0; i <= length1; i ++ )    maxLen[i][0] = 0;
        for( j = 0; j <= length2; j ++ )    maxLen[0][j] = 0;

        for( i = 1; i <= length1; i ++ )
        {
            for( j = 1; j <= length2; j ++ )
            {
                if( sz1[i-1] == sz2[j-1] )         maxLen[i][j] =  maxLen[i-1][j-1] + 1;
                else          maxLen[i][j] = max(maxLen[i][j-1], maxLen[i-1][j]);
            }
        }
        cout <<  maxLen[length1][length2] << endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。