最長公共子序列是經(jīng)典的動態(tài)規(guī)劃問題，在很多書籍和文章中都有介紹，這里對這一經(jīng)典算法進行回顧并對兩個follow up questions進行總結(jié)和分析。

1. 回顧LCS（longest common subsequence）解法，求LCS長度

典型的雙序列動態(tài)規(guī)劃問題，dp[i][j]表示第一個序列前i項與第二個序列的前j項....

所以對應(yīng)此題，dp[i][j]表示序列s1的前i項與序列s2的前j項的最長公共子序列。

得到如下遞推關(guān)系式：

dp[i][j] = dp[i - 1][j - 1] + 1 ? ? ? ? ? ? ? ? ?if s1[i - 1] == s2[j - 1]

　　　　= max(dp[i - 1][j], dp[i][j - 1]) ? if s1[i - 1] != s2[j - 1] ;

對dp[0][j] j = 0,1,... 于 dp[i][0] i = 0,1...初始化，根據(jù)遞推關(guān)系式則可以得到結(jié)果。

程序：

1 int longsetCommonSubsequence(const string& s1, const string& s2) { 2 int sz1 = s1.size(), sz2 = s2.size(); 3 int dp[sz1 + 1][sz2 + 1]; 4 for (int i = 0; i <= sz1; ++i) { 5 dp[i][0] = 0; 6 } 7 for (int i = 0; i <= sz2; ++i) { 8 dp[0][i] = 0; 9 } 10 for (int i = 1; i <= sz1; ++i) { 11 for (int j = 1; j <= sz2; ++j) { 12 if (s1[i] == s2[j]) { 13 dp[i][j] = dp[i - 1][j - 1] + 1; 14 } 15 else { 16 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 17 } 18 } 19 } 20 return dp[sz1][sz2]; 21 }

?

2. 如何得到最長公共子序列？

其實本質(zhì)上，當有了dp數(shù)組時，即得到了行程LCS的所有信息。

我們考察一個例子，求s1 = "ABCBDAB" 和 s2 = "BDCABA"的 LCS， 得到其dp數(shù)組如下。（圖片來自鄒博）

我們可以看到，當dp數(shù)組被填充完畢后。反向探索LCS的形成過程，結(jié)合遞推公式可知，每一個添加到LCS中的字符是在s1[i - 1] == s2[j - 1]的情況下加入的。

也就是上述圖中向同時向左上方的那些步驟，而對應(yīng)s1[i - 1] != s2[j - 1]的那些步驟，則選擇其dp值大的（原因在于生成的時候路徑就是選的max）進行前進即可。

所以總結(jié)尋找LCS的算法步驟即：

如果s1[i - 1] == s2[j - 1]，將其push_back到結(jié)果中；

如果s1[i - 1] != s2[j - 1]，選擇dp[i - 1][j]與dp[i][j - 1]中大的更新i--或j--。

直到i或者j達到0后，翻轉(zhuǎn)上述結(jié)果即可。

代碼：

1 string longsetCommonSubsequence2(const string& s1, const string& s2) { 2 int sz1 = s1.size(), sz2 = s2.size(); 3 int dp[sz1 + 1][sz2 + 1]; 4 for (int i = 0; i <= sz1; ++i) { 5 dp[i][0] = 0; 6 } 7 for (int i = 0; i <= sz2; ++i) { 8 dp[0][i] = 0; 9 } 10 for (int i = 1; i <= sz1; ++i) { 11 for (int j = 1; j <= sz2; ++j) { 12 if (s1[i - 1] == s2[j - 1]) { 13 dp[i][j] = dp[i - 1][j - 1] + 1; 14 } 15 else { 16 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 17 } 18 } 19 } 20 string result; 21 int i = sz1, j = sz2; 22 while (i > 0 && j > 0) { 23 if (s1[i - 1] == s2[j - 1]) { //對應(yīng)的是s1[i - 1]， s2[j - 1] 24 result.push_back(s1[i - 1]); 25 i--; 26 j--; 27 } 28 else { 29 if (dp[i - 1][j] > dp[i][j - 1]) { 30 i--; 31 } 32 else { 33 j--; 34 } 35 } 36 } 37 reverse(result.begin(), result.end()); 38 return result; 39 }

?

3. 有多組解都要輸出怎么辦？

首先考慮什么時候會有多組解？還考慮上述圖示可以發(fā)現(xiàn)，當s1[i - 1] != s2[j -1]但 dp[i - 1][j] == dp[i][j - 1]時，i--， j--均可。所以可能產(chǎn)生多組解。

想要輸出所有解的想法其實也很直觀，就是DFS，把所有情況都遍歷一遍，并進行去重(代碼中find語句)，把不同路徑的相同解刪除掉，即可得到所有解。

一段完整的，帶簡單測試的程序如下：

1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 vector<int> temp; 7 vector<vector<int>> resultIndex; 8 void dfs(const vector<vector<int>>& dp, const string& s1, const string& s2, int i, int j) { 9 if (i == 0 || j == 0) { 10 if (find(resultIndex.begin(), resultIndex.end(), temp) == resultIndex.end()) { 11 resultIndex.push_back(temp); 12 } 13 return ; 14 } 15 if (s1[i - 1] == s2[j - 1]) { 16 temp.push_back(i - 1); 17 dfs(dp, s1, s2, i - 1, j - 1); 18 } 19 else { 20 if (dp[i - 1][j] > dp[i][j - 1]) { 21 dfs(dp,s1,s2,i - 1, j); 22 } 23 else if (dp[i - 1][j] < dp[i][j - 1]) { 24 dfs(dp, s1, s2, i, j - 1); 25 } 26 else { 27 vector<int> temp2 = temp; 28 dfs(dp,s1,s2,i - 1, j); 29 temp = temp2; 30 dfs(dp,s1,s2,i, j - 1); 31 } 32 } 33 return; 34 } 35 36 vector<string> longsetCommonSubsequence2(const string& s1, const string& s2) { 37 int sz1 = s1.size(), sz2 = s2.size(); 38 vector<vector<int>> dp(sz1 + 1,vector<int>(sz2 + 1)); 39 for (int i = 0; i < sz1; ++i) { 40 dp[i][0] = 0; 41 } 42 for (int i = 0; i < sz2; ++i) { 43 dp[0][i] = 0; 44 } 45 for (int i = 1; i <= sz1; ++i) { 46 for (int j = 1; j <= sz2; ++j) { 47 if (s1[i - 1] == s2[j - 1]) { 48 dp[i][j] = dp[i - 1][j - 1] + 1; 49 } 50 else { 51 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 52 } 53 } 54 } 55 vector<string> result; 56 dfs(dp,s1,s2,sz1,sz2); 57 for (int i = 0; i < resultIndex.size(); ++i) { 58 string s; 59 result.push_back(s); 60 for (int j = resultIndex[i].size() - 1; j >= 0; --j) { 61 result[i].push_back(s1[resultIndex[i][j]]); 62 } 63 } 64 return result; 65 66 } 67 68 int main() { 69 string s1 = "ABCBDAB", s2 = "BDCABA"; 70 vector<string> result = longsetCommonSubsequence2(s1,s2); 71 for (int i = 0; i < result.size(); ++i) { 72 cout << result[i] << endl; 73 } 74 return 0; 75 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wangxiaobao/p/5982901.html

總結(jié)

以上是生活随笔為你收集整理的最长公共子序列及其引申问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。