基本概念：
子序列：
給定序列：{a,b,c,d,e,f}
則{a,b,c},}{a,c,f},{d,f}都是子序列
最長公共子序列：
給定兩個序列
A：{a,b,c,d,e,f}
B：{a,c,e,g}
則A和B都有子序列{a,c,e}，而最長公共子序列就是指既是A的子序列又是B的子序列，而且要保證是最長。是以A和B的最長公共子序列為{a,c,e}，長度為3。
一、問題描述
給定兩個字元串，求出這兩個字元串的最長公共子序列(LCS)
二、解題方法
暴力法：序列A有 2^n 個子序列，序列B有 2^m 個子序列，如果任意兩個子序列一一比較，比較的子序列高達 2^(n+m) 對，(不推薦)。
動态規劃：動态規劃法（dynamic programming）通常用于求解最優化問題（optimization problem），它适用于那些子問題互相重疊的情況，即子問題不獨立，不同的子問題具有公共的子子問題（就是子問題的子問題）。經常會遇到複雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地采用把大問題分解成子問題，并綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規模呈幂級數增加。
為了節約重複求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存于該數組中，這就是動态規劃法所采用的基本方法。
用一張圖解釋這個公式：
例子：
兩個char數組a=[r,a,n,d,o,m]，b=[a,n,d,r,o,i,d]，還有一個dp數組用二維數組表示：
第一步：初始化二維數組第一行和第一列
第一行：
00位置a和r比較—不相等—指派0，
01位置a和a比較—相等—指派1，接着01後面的02，03，04，05，06全部為指派1，第一行初始化完畢，代表目前已找到1個符合的LCS。
for(int i = 0;i<m;i++){ //建構第一行
if(a[0] == b[i]){ //如果值相等
dp[0][i] = 1; //其位置為1
for(int j = i+1;j<m;j++){ //後面的值全部為1
dp[0][j] = 1;
}
break;
}
}
第一列同理：
00位置 a和r比較—不相等—指派0，
10位置 n和r比較—不相等—指派0，
20位置 d和r比較—不相等—指派0，
30位置 r和r比較—相等—指派1，接着40，50，60，70全部為指派1，第一列初始化完畢。
for(int i = 0;i<n;i++){ //建構第一列
if(a[i] == b[0]){ //如果值相等
dp[i][0] = 1; //其位置為1
for(int j = i+1;j<n;j++){ //後面的值全部為1
dp[j][0] = 1;
}
break;
}
}
第二步：從二維數組[1,1]位置開始按公式規則指派下去
解釋：
11位置 a和n比較—不相等—指派Max[(i,j-1),(i-1,j)]=Max[0,1]=1
12位置 n和n比較—相等—指派(i-1,j-1)+1=1+1=2
13位置 d和n比較—不相等—指派Max[(i,j-1),(i-1,j)]=Max[2,1]=2
14位置 o和n比較—不相等—指派Max[(i,j-1),(i-1,j)]=Max[2,1]=2
不在贅述…
最後結果：
最終代碼：
public class LCS {
public int findLCS(String A,String B){ //傳入ab兩個串
int n = A.length(); //擷取長度
int m = B.length();
char[] a = A.toCharArray(); //轉化為數組
char[] b = B.toCharArray();
int [][] dp = new int[n][m]; //建立動态規劃的二維數組
for(int i = 0;i<n;i++){ //建構第一列
if(a[i] == b[0]){ //如果值相等
dp[i][0] = 1; //指派為1
for(int j = i+1;j<n;j++){ //後面的值全部為1
dp[j][0] = 1;
}
break;
}
}
for(int i = 0;i<m;i++){ //建構第一行
if(a[0] == b[i]){ //如果值相等
dp[0][i] = 1; //指派為1
for(int j = i+1;j<m;j++){ //後面的值全部為1
dp[0][j] = 1;
}
break;
}
}
for(int i = 1;i<n;i++){ //周遊每行 指派除第一行和第一列之外的角标
for(int j = 1;j<m;j++){ //周遊每行的每個元素
if(a[i] == b[j]){ //相等
dp[i][j] = dp[i-1][j-1]+1; //值為其左上值+1
}else{ //不相等
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); //值為左和上取較大的值
}
}
}
for(int i = 0;i<n;i++){ //輸出控制台
for(int j = 0;j<m;j++){
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
return dp[n-1][m-1];
}
public static void main(String [] args){
LCS lcs = new LCS();
int findLCS = lcs.findLCS("random", "android");
System.out.println("最長子序列長度："+findLCS);
}
}
結果圖：