***哈哈，能破解密碼的人【計算機考研】一定過！！！ *** 題目描述： ACM俱樂部的墻上寫著兩行密碼字符串，據說能破解其中奧秘的人計算機考研一定過。 如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，則字符串一稱之為字符串二的子串。 注意，并不要求子串（字符串一）的字符必須連續出現在字符串二中。 現在求ACM俱樂部兩行密碼字符串的最長公共子串的長度。 輸入格式： 每組測試數據輸入兩行，每行輸入一個字符串（長度<=100）。 輸出: 每組測試數據輸出一行，輸出ACM俱樂部兩行密碼字符串的最長公共子串的長度。 樣例輸入: BDCABA ABCBDAB JXVTEWSNHACJDE LDAAJNOPPERLJBPUUNHWSYYODMGW 樣例輸出: 4 5 **我的分析：** 假想： 對于兩個字符串x和y，有對應子串a和b,假如a和b的最長公共子 序列的長度為j, 那么c和d分別為其后面字符，ac和b的最長公共子序列的長度為 k, a和bd的最長公共子序列的長度為h; 有兩種情況： 1.c和d相同，那么ac和ad的最長公共子序列的長度為j+1 2.c和d不相同，那么ac和ad的最長公共子序列的長度可能為k或 h或j 但是不論什么情況,我們只需找出這三個數的最大值 問題是j,k,h不知？？？ 例:BDCABA |—— ABCBDAB 我們從A-B統計直到最后 程序的編寫： 我想到了二維數組，用me[a][b]表示兩個字符串a位和b位最長 公共子序列的長度,即 me[a+1][b+1]=(me[a+1][b],me[a][b+1],me[a][b]或me[a][b]+1） 的最大值  對于任意的數組，只要邊緣的數組確定了，其它的數也就確定了. 最后x和y最長公共子序列的長度就為n。 我的代碼： ~~~ import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); String str1,str2; while(in.hasNextLine()){ str1=in.nextLine(); str2=in.nextLine(); int[][] me=new int[str1.length()][str2.length()];//創建一個以兩個字串的長度為行列的二維數組 int oo=0; for(int j=0;j<str2.length();j++) { if(str1.charAt(0)==str2.charAt(j)&&oo==0) {me[0][j]=1;oo=1;} if(oo==1) me[0][j]=1; } oo=0; for(int j=0;j<str1.length();j++) { if(oo==0&&str1.charAt(j)==str2.charAt(0)){ me[j][0]=1;oo=1;} if(oo==1) me[j][0]=1; }//把數組的邊緣的長度填充完整 int a=1,b=0; while(a<str1.length()||a<str2.length()){//填充余下的數 b=a; if(b>=str1.length()) b=str1.length()-1; if(b-1<0) break; for(int j=a;j<str2.length();j++) { if(str1.charAt(b)==str2.charAt(j)) me[b][j]=Max(me[b][j-1],me[b-1][j],me[b-1][j-1]+1); else me[b][j]=Max(me[b][j-1],me[b-1][j],me[b-1][j-1]); } b=a; if(b>=str2.length()) b=str2.length()-1; if(b-1<0) break; for(int j=a;j<str1.length();j++) { if(str1.charAt(j)==str2.charAt(b)) me[j][b]=Max(me[j][b-1],me[j-1][b],me[j-1][b-1]+1); else me[j][b]=Max(me[j][b-1],me[j-1][b],me[j-1][b-1]); } a++; } System.out.println(me[str1.length()-1][str2.length()-1]); } } public static int Max(int a,int b,int c){//方法：求三個數的最大值 int max=a; if(b>max) max=b; else if(c>max) max=c; return max; } } ~~~ //這道題實質是要用算法【動態規劃】，但我自己對動態規劃不很理解，只能自己分析