1.两个子序列：X={x,x....x}，Y={yyy}，设Z={z,z...z}。
2.最优子结构：
1）如果x=y，则z=x=y且Z是X和Y的一个LCS。
2）如果x!=y，则z!=x包含Z是X和Y的一个LCS。
3）如果x!=y，则z!=y包含Z是X和Y的一个LCS。
3.则由最优子结构可得递归式：
4.实现：
#include<string>
#include<iostream>
using namespace std; int arr[][] = {};
void LCS(string str1, string str2){
int len1 = str1.length();
int len2 = str2.length();
//边界
for (int i = ; i <= len1; i++)
arr[i][] = ;
for (int j = ; j <= len2; j++)
arr[][j] = ;
//检验
for (int i = ; i <= len1; i++)
{
for (int j = ; j <= len2; j++)
{
if (str1[i - ] == str2[j - ]) //记录
{
arr[i][j] = arr[i - ][j - ] + ;
}
else if (arr[i][j - ] >= arr[i - ][j])
{
arr[i][j] = arr[i][j - ];
}
else
{
arr[i][j] = arr[i - ][j];
}
}
}
} void printLCS(string str1, string str2,int len1, int len2){
cout << "最长公共子序列长为：" << arr[len1][len2] << endl;
//倒序输出
while (len1&&len2){
if (str1[len1-]==str2[len2-])
{
cout << str1[len1 - ];
len1--;
len2--;
}
else if (arr[len1][len2-]>=arr[len1-][len2])
{
len2--;
}
else{
len1--;
}
}
cout << endl;
} int main()
{
string str1 = "abcdsnnnn";
string str2 = "acbdanm";
LCS(str1, str2);
printLCS(str1, str2,str1.length(), str2.length());
return ;
}