算法設計例題：最長公共子序列（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; }
