最长公共子序列（DP）
算法设计例题：最长公共子序列（DP）
memory limit: 65536KB time limit: 500MS
accept: 50 submit: 124
Description
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 X = { x1，x2，…，xm }，则另一序列Z={ z1，z2，…，zk }，X的子序列是指存在一个严格递增下标序列{ i1，i2，…，ik }，使得对于所有 j = 1，2，…，k ，有 zj = xij
给出两个字符序列X和Y，求出它们的最长公共子序列。
Input
输入的第一行为测试样例的个数T（ T < 40 ），接下来有T个测试样例。每个测试样例的第一行是字符串X，第二行是字符串Y。X和Y只包含大写字母，且长度不大于1000。
Output
对应每个测试样例输出一行，只有一个整数，表示字符串X和字符串Y的最长公共子序列的长度。
Sample Input
2
ABCDE
ACE
AAABBBCCC
AABBCC
Sample Output
3
6
Author
Eapink & CYL
解决方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<string.h>
#define
N 1000
int
dp[N][N];
int
max(int
a,int
b)
{
return
a>b?a:b;
}
int
main()
{
int
i,j,k,len1,len2,textNum;
char
s1[N],s2[N];
scanf("%d",&textNum);
for(k=0;k<textNum;k++)
{
scanf("%s%s",s1,s2);
len1=strlen(s1);
len2=strlen(s2);
for(i=1;i<len1;i++)
dp[i][0]=0;
for(j=1;j<len2;j++)
dp[0][j]=0;
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
if(s1[i-1]==s2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
printf("%d\n",dp[len1][len2]);
}
return
0;
}
补充：软件开发 , C++ ,
