數據結構與演算法：動態規劃之LCS最長公共子序列

什麼是最長公共子序列？

就是兩個數組能夠組成的最大相同的子序列。

這裡通過具體的例子來進行分析：

給定兩個字元串A和B，返回兩個字元串的最長公共子序列的長度。例如，A="1A2C3D4B56」，B="B1D23CA45B6A」，」123456"或者"12C4B6"都是最長公共子序列。給定兩個字元串A和B，同時給定兩個串的長度n和m，請返回最長公共子序列的長度。保證兩串長度均小於等於300

面對這個問題，如果不使用特殊的策略，而使用暴力搜索那麼時間複雜度一定會爆表。關鍵在於子序列不一定是連續的子序列，可以是不連續的。所以類似問題我們一般使用動態規劃來解決問題。

以下是分析過程：

下面使用來實現這種思路：

public static int findLCS(String A, int n, String B, int m) { //創建dp數組 int[][] dp=new int[n][m]; //將字元串轉化為char數組 char[] a=A.toCharArray(); char[] b=B.toCharArray(); //初始化第一列,出現相同的，將後面全部置為1 int i=0; for(;i<n;i++){ if(a[i]==b[0]){ break; } } for(;i<n;i++){ dp[i][0]=1; } //初始化第一行,出現相同的，將後面全部置為1 int j=0; for(;j<m;j++){ if(b[j]==a[0]){ break; } } for(;j<m;j++){ dp[0][j]=1; } for(i=1;i<n;i++){ for(j=1;j<m;j++){ if(a[i]==b[j]){ //求出三者中的最大值 dp[i][j]=dp[i-1][j-1]+1; }else{ dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[n-1][m-1]; }

推薦閱讀：