名詞解釋：
sadstory與adminsorry的最長(zhǎng)公共子序列是adsory摆昧，長(zhǎng)度為6号阿。
dp的值代表在該(i,j)串中已匹配的個(gè)數(shù)争便。
走過來的路徑：
對(duì)A與B兩個(gè)字符串怎静，取A[i]媚污，B[j]為例：
- 若A[i]==B[j]：
A[i]與B[j]可以組成一對(duì)新的公共子序列舀瓢，所以dp[i][j]==dp[i-1][j-1]+1
- 若A[i]!=B[j]：
i或者j中至少有一個(gè)不能成為公共子序列的成員，因?yàn)閕!=j耗美，所以i必須跟j之前的配對(duì)京髓，那么j就涼了，所以dp[i][j]==dp[i][j-1]幽歼，或者dp[i][j]==dp[i-1][j]朵锣，看誰更大（配對(duì)多）就選哪個(gè)。
但是如果出現(xiàn)相等的話怎么辦甸私？-->走兩邊都能得出正確的解
image.png
求過來的路徑：
image.png
如果a[i]诚些，b[j]處字符相等，打印點(diǎn)，x--诬烹，y--
if(a[x-1]==b[y-1]){
cout<<a[x-1]<<">>";
x--;
y--;
}
如果字符不相等砸烦，則選擇dp大的一邊走，如果dp[x-1][y]與dp[x][y-1]相等绞吁，則會(huì)有兩種走法進(jìn)而演化出多種不同的可能幢痘，如果考這個(gè)的話可以用DFS遞歸解。
else{
if(dp[x-1][y]>dp[x][y-1]){
x--;
}
else{
y--;
}
}
遍歷所有可能子序列的解法:
void tracefullpath(int i,int j,vector<int>vv){
if(i>=1&&j>=1){
if(a[i-1]==b[j-1]){
//cout<<"-->";
vv.push_back(i-1);
tracefullpath(i-1,j-1,vv);
}
else if(dp[i-1][j]==dp[i][j-1]){
tracefullpath(i-1,j,vv);
tracefullpath(i,j-1,vv);
}
else if(dp[i-1][j]>dp[i][j-1]){
tracefullpath(i-1,j,vv);
}
else{
tracefullpath(i,j-1,vv);
}
}
else{
print(vv);
return;
}
}
測(cè)試數(shù)據(jù)：
abcfbc abfcab
programming contest
abcd mnp
4
2
0
示例代碼：
#include <bits/stdc++.h>
using namespace std;
#define N 1000
int points,edges;
char a[N];
char b[N];
// i是從1到n的家破，所以字符串匹配是a[i-1]而不是a[i]
// char數(shù)組從0開始颜说，dp從1開始，要注意
int dp[N][N]={0};
// 根據(jù)原操作逆向出原路徑汰聋。
void chase_path(int x,int y){
cout<<"path: ";
while(y>=1&&x>=1){
if(a[x-1]==b[y-1]){
cout<<a[x-1]<<">>";
x--;
y--;
}
else{
if(dp[x-1][y]>dp[x][y-1]){
x--;
}
else{
y--;
}
}
}
}
int main() {
int i,j;
scanf("%s %s",&a,&b);
int len_a=strlen(a);
int len_b=strlen(b);
// 獲取字符串長(zhǎng)度
for(i=1;i<len_a+1;i++){
for(j=1;j<len_b+1;j++){
if(a[i-1]==b[j-1]){
// char數(shù)組從0開始门粪，所以要a/b要-1
dp[i][j]=dp[i-1][j-1]+1;
// 在ij未放入的時(shí)候最優(yōu)基礎(chǔ)上+1
}
else{
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
// 如果i，j放了跟沒放一樣烹困，那么就跟dp[i][j-1]/dp[i-1][j]一樣了
}
}
}
cout<<"\nCommon Length:"<<dp[len_a][len_b];
return 0;
}
