最長公共子序列
文章有些長，希望能夠耐心看完，并且對你有幫助，文章是自己看了書之后，總結(jié)的，如果有什么錯誤的地方，歡迎指出。
一些基本的概念：
子序列： 原序列中刪除若干個元素得到的序列，即原序列中可以不連續(xù)的一段
子串： 原序列中任意個連續(xù)的序列元素組成的序列，即原序列中必須連續(xù)的一段。
（兩者的元素順序必須和原序列中的順序一樣）
最長公共子序列： 一個序列即是X序列的子序列，也是Y序列的子序列，則該序列稱為為X和Y的公共子序列。對于兩個序列的公共子序列是不唯一的，因此，最長公共子序列顧名思義就是長度最長的公共子序列。
思路分析：
方一、從最優(yōu)子結(jié)構(gòu)去考慮
求最長公共子序列長度：
分析：
? 因為動態(tài)規(guī)劃的題目是滿足最優(yōu)子結(jié)構(gòu)（最優(yōu)解包含其子問題的最優(yōu)解）這一基本條件的，因此我們通過分析最優(yōu)子結(jié)構(gòu)的特征，從而推出最優(yōu)值的遞推式，然后從子問題最優(yōu)解出發(fā)，求解出整個問題的最優(yōu)解即可。
? 假設(shè)一個最優(yōu)子結(jié)構(gòu)情況，對于一個序列Z = {z1， z2， …… ， zk}是 X = {x1, x2, ……, xm} 和 Y ={y1， y2 , ……， yn}的最長公共子序列，根據(jù)對最后一個元素考慮，我們可以分成三種情況來具體討論：
1）xm = yn = zk
? 將xm和yn的值作為序列Z的最長公共子序列的最后一個元素，如果去掉xm和yn，那么對于序列Z的最長公共子序列的長度肯定會減小1，即c[i - 1] [j - 1] = c[i] [j] - 1; 因此，當xm = yn時的遞推公式是： c[i] [j] = c[i - 1] [j - 1] + 1；
（為什么要將xm和yn值做為最長公共子序列最后一個元素？你想，兩個序列相等的元素且都在最后一個，并且和已知最長公共子序列的最后一個元素相等，無論X和Y前面怎么取公共部分，是不是最后這兩個元素都可以作為一個公共部分加入到公共子序列的末尾）
2）xm ≠ yn, xm ≠ zk
? 表明xm肯定不會作為最長公共子序列的最后一個元素，那么我們把xm去掉，對于{x1， x2，……， xm-1} 和 {y1， y2，……， yn -1}的最長公共子序列也還是{z1， z2，……， zk-1}
3）xm ≠ yn, yn ≠ zk
? 同理2）情況
由1）2）3）得最優(yōu)值的遞推式：
對于c[i] [j]數(shù)組：指只取X前i個元素和只取Y前j個元素能夠得到的最長公共子序列的值（即存放最優(yōu)子結(jié)構(gòu)的值）。
由1）可知，如果xi = yj，那么可以從沒有xi和yj的最優(yōu)子結(jié)構(gòu)即c[i - 1] [j - 1]轉(zhuǎn)移過來
即 c[i] [j] = c[i - 1] [j - 1] + 1；
由2）3）可知，如果xi ≠ yj, 那么我們只需要取xi和yj-1最優(yōu)子結(jié)構(gòu)和xi-1和yj最優(yōu)子結(jié)構(gòu)的最大長度即可。
即c[i] [j] = max（c[i] [j - 1] ， c[i - 1] [j] ）；
綜上可以得出遞推式：
自底向上求出問題的最優(yōu)解：
? 對子結(jié)構(gòu)考慮的最優(yōu)情況，得出的遞推式是對所有求子問題的最優(yōu)解適用的，通過該遞推公式，自底向上計算子問題的最優(yōu)值，那么最后的答案也肯定是最優(yōu)的（這也就是動態(tài)規(guī)劃的最優(yōu)子結(jié)構(gòu)的特征）
代碼：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
char s1[N], s2[N];
int len1, len2;
int c[N][N];
int main()
{
//最優(yōu)子結(jié)構(gòu)狀態(tài)值初始化（當然也可以不寫，因為全局變量默認為0）
memset(c, 0, sizeof(c));
//輸入序列s1和s2的長度
cin>>len1>>len2;
//輸入需要求最長公共子序列的序列s1和s2
cin>>s1+1>>s2+1;
for(int i = 1; i <= len1; i ++){
for(int j = 1; j <= len2; j ++){
if(s1[i] == s2[j])c[i][j] = c[i - 1][j - 1] + 1;
else c[i][j] = max(c[i - 1][j], c[i][j - 1]);
}
}
cout<<c[len1][len2]<<'\n';
return 0;
}
求最長公共子序列內(nèi)容：
分析：
對于一個最優(yōu)子結(jié)構(gòu)c[i] [j]的來源一共有三個，分別是
1）c[i] [j] = c[i - 1] [j - 1] + 1；
2）c[i] [j] = c[i - 1] [j] ；
3）c[i] [j] = c[i] [j - 1]；
在自底向上計算最優(yōu)值的時候，我們可以開一個臨時的數(shù)組b[i] [j]去記錄這3個來源，然后根據(jù)最值反向追蹤最長公共子序列:
1)b[i] [j] = 1, 即表示取了x[i]或y[j]作為最長公共子序列的一部分，我們輸出即可。
2）b[i] [j] = 2，即表示當前c[i] [j]的狀態(tài)來自c[i - 1] [j],我們追蹤c[i - 1] [j]
3）b[i] [j] = 3， 即表示當前c[i] [j]的狀態(tài)來自c[i] [j - 1],我們追蹤c[i] [j - 1]
代碼：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
char s1[N], s2[N];
int len1, len2;
int c[N][N];
int b[N][N];
void print(int i, int j){
if(i == 0 || j == 0)return;
if(b[i][j] == 1){
print(i - 1, j - 1);
cout<<s1[i];
}
else if(b[i][j] == 2)print(i - 1, j);
else print(i, j - 1);
}
int main()
{
//最優(yōu)子結(jié)構(gòu)狀態(tài)值初始化
memset(c, 0, sizeof(c));
//輸入序列s1和s2的長度
cin>>len1>>len2;
//輸入需要求最長公共子序列的序列s1和s2
cin>>s1+1>>s2+1;
for(int i = 1; i <= len1; i ++){
for(int j = 1; j <= len2; j ++){
if(s1[i] == s2[j]){
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else if(c[i - 1][j] >= c[i][j - 1]){
c[i][j] = c[i - 1][j];
b[i][j] = 2;
}
else {
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
}
print(len1, len2);
// cout<<c[len1][len2]<<'\n';
return 0;
}
當然如果你不想浪費空間，你也可以不用這個臨時數(shù)組b，直接通過c數(shù)組判斷即可：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
char s1[N], s2[N];
int len1, len2;
int c[N][N];
void print(int i, int j){
if(i == 0 || j == 0)return;
if(c[i][j] == c[i - 1][j - 1] + 1){
print(i - 1, j - 1);
cout<<s1[i];
}
else if(c[i][j] == c[i - 1][j])print(i - 1, j);
else print(i, j - 1);
}
int main()
{
//最優(yōu)子結(jié)構(gòu)狀態(tài)值初始化
memset(c, 0, sizeof(c));
//輸入序列s1和s2的長度
cin>>len1>>len2;
//輸入需要求最長公共子序列的序列s1和s2
cin>>s1+1>>s2+1;
for(int i = 1; i <= len1; i ++){
for(int j = 1; j <= len2; j ++){
if(s1[i] == s2[j])c[i][j] = c[i - 1][j - 1] + 1;
else c[i][j] = max(c[i - 1][j], c[i][j - 1]);
}
}
print(len1, len2);
//cout<<c[len1][len2]<<'\n';
return 0;
}
方二、閆氏DP分析法（從集合的角度考慮）：
分析：
很久之前在Acwing上學(xué)習(xí)后，寫的題解（字丑）：
我們通過f[i] [j]去表示所有A[1 ~ i]和B[1 ~ j]的公共子序列的集合，其表示的屬性是最大值（即最長長度）。
我們通過最長公共子序列是否包含最后兩個元素即a[i]和b[j]對這個集合來進行劃分,可以分為4種情況：
- a[i]和b[j]相等
- a[i]和b[j]不相等，a[i]和bx匹配x在j之前
- a[i]和b[j]不相等，b[j]和ax匹配x在i之前
- a[i]和b[j]不相等，兩數(shù)都沒有匹配
對于f[i] [j] = f[i - 1] [j - 1] + 1覆蓋情況1
對于f[i] [j] = max{f[i - 1] [j], f[i] [j - 1]}覆蓋情況2 3 4文章來源：http://www.zghlxwxcb.cn/news/detail-413587.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-413587.html
代碼：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 5;
int n, m;
int f[N][N];
char a[N], b[N];
int main()
{
cin >> n;
cin >> a + 1;
cin >> m;
cin >> b + 1;
for(int i = 1; i <= n; i ++)f[i][0] = i;
for(int j = 1; j <= m; j ++)f[0][j] = j;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
int diff;
if(a[i] == b[j])diff = 0;
else diff = 1;
f[i][j] = min({f[i - 1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + diff});
}
}
// for(int i = 0; i <= n; i ++){
// for(int j = 0; j <= m; j ++){
// cout << f[i][j] << ' ';
// }
// cout << '\n';
// }
cout << f[n][m] << '\n';
return 0;
}
/*
狀態(tài)表示：
集合：a前i 變成b前j需要的操作
屬性：min
狀態(tài)計算：
劃分：根據(jù)最后一個元素從增、刪、改進行劃分
//替
1)A[i] == B[j] 不用進行操作
f[i][j] = f[i - 1][j - 1];
2)A[i] != B[j]
f[i][j] = f[i - 1][j - 1] + 1;
3)A[i] 增B[j]（ai 和 bj - 1 對齊）
f[i][j] = f[i][j - 1] + 1;
4)A[i] 刪 A[i]（ai - 1 和 bj 對齊）
f[i][j] = f[i - 1][j] + 1;
狀態(tài)轉(zhuǎn)移：
*/
//狀態(tài)表示：f[i][j]是以1~ai的序列和以1~bj的序列的最長的公共子序列長度
//當枚舉到的兩個元素相同時：
//說明可以將該元素加入到兩個子序列的最長公共子序列上，因此就直接對于f[i][j]=f[i-1][j-1]+1,表示在1~a[i-1]和
//1~b[j-1]的公共最長子序列的基礎(chǔ)上加1,將f[i-1][j-1]狀態(tài)加一轉(zhuǎn)移給f[i][j]
//因此我們轉(zhuǎn)移公式就是：f[i][j]=f[i-1][j-1]+1
//當枚舉到的兩個元素不同：
//那我們肯定是不能夠?qū)⑺麄兗尤氲絻蓚€子序列的最長公共子序列上，因此我們要去尋找之前最長的公共子序列長度轉(zhuǎn)移過來
//對于a[i]和b[j]不相等存在3中情況：
//1、a[i]屬于a和b的最長公共子序列，a[i]和bx匹配x在j之前，那么我們就要從f[i][j-1]將狀態(tài)轉(zhuǎn)移過來，此時的狀態(tài)就
//是到i，j為止最長的公共子序列長度
//2、b[j]屬于a和b的最長公共子序列，b[j]和ax匹配x在i之前，那么我們就要從f[i-1][j]將狀態(tài)轉(zhuǎn)移過來此時的狀態(tài)就是
//到i，j為止最長的公共子序列長度
//3、a[i]和b[j]都不屬于a和b的最長公共子序列，我們應(yīng)當是從f[i-1][j-1]去將狀態(tài)轉(zhuǎn)移過來，但對于f[i-1][j]和f[i][j-1]
//是已經(jīng)將f[i-1][j-1]的狀態(tài)包括在里面（因為這三者是相等的）
//因此我們轉(zhuǎn)移公式就是：f[i][j]=max(f[i][j-1],f[i-1][j])
到了這里，關(guān)于最長公共子序列（詳細代碼 注釋 分析 以及求出最長公共子序列內(nèi)容方法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
