求解两个数组的最长公共子序列我们需要用到的知识点有：动态规划dp，递归算法
先来说说动态规划dp 很多初学者在学习动态规划的时候总是百思不得其解，什么是动态规划呢，其实总结来说就是程序将计算过的结果记录下来，在下次使用到这条记录的时候不需要再次计算，而可以直接使用，这样看来是不是节省了很大的时间开销呢！
动态规划解决问题一般套路可以分为两步，1：自顶向下的分析问题 2：自底向上的解决问题
为什么要自顶向下的分析问题呢？ 我们要知道问题在多数值的情况下往往会具有一般性。
而自底向上的解决问题则是因为数据是从最底的数据开始记录，由少的数值计算得出多的数值。
我们可以用盖房子为例子，工程师是负责设计架构的，一般是从房子的头部开始向下设计，而建造房子则是需要从最底部开始搭建，所以自顶向下的设计，自底向上的解决。
现在回到我们的问题上，求两个字符串的最长序列，假设第一个字符串为S1，字符长度为i，第二个字符串为S2，字符长度为j。建立二维数组dp[i+1][j+1]，dp[i][j]的意思为第一个字符串的前i个与第二个字符串的前j个的最长子序列。我们自顶向下的分析问题即从S1的最后一个即第i个与S2的最后一个即第j个进行判断。显而易见可以看出假如S1[i]==S2[j]相等的话那么i与j判断完毕，接下来就从i-1与j-1开始判断（因为i与j判断完毕就往前判断）故dp[i][j]=dp[i-1][j-1]+1。
假如S1[i]==S2[j]不相等的话，那么会出现两种情况，要知道最大子序列是两者共有的，那么i和j不相等，他们之中一定有一个不在子序列当中，所以要么i不在，要么j不在，i不在那么我们就从i-1开始找，j不在我们就从j-1开始找。故dp[i][j]=max(dp[i-1][j],dp[i][j-1])。
代码如下：
for(int p=1;p<=i;p++)// i为S1的长度 p，q皆从1开始往后面循环
{
for(int q=1;q<=j;q++) //j为S2的长度 自底向上解决问题
{
if(s1[p-1]==s2[q-1]) //字符串从0开始 这里容易出错
{
dp[p][q]=dp[p-1][q-1]+1;
}
else
{
dp[p][q]=max(dp[p-1][q],dp[p][q-1]);
}
}
}这样我们就可以得到最长子序列的长度了，可以这样我们无法得知最长子序列到底是什么样的？
想要得出这个结果，我们就需要使用递归来解决。
在先前我们已经得出了dp数组的完整数值，我们可以使用dp数组的值递归来解决，我们先准备一个空数组，假如S1[i]==S[j]，那么我们就可以直接把这个值记录到数组里，假如他们不相等，那么就是上面的情况了分别是i不在和j不在。具体我们已经通过dp计算出来了即dp[i][j]==dp[i-1][j]那么就是i不在序列中，我们从S1的第1个到i-1个与S2的第1个到第j个开始寻找。dp[i][j]==dp[i][j-1]那么就是j不在序列中，我们从S1的第1个到i个与S2的第1个到第j-1个开始寻找。这样重复递归，当i等于0或者j为0时停止递归。
代码如下：
void found(string a,string b,int i,int j,char rem[],int dp[][100]){
if(i==0 ||j==0){
return;
}
if(a[i-1]==b[j-1])
{
rem[m]=a[i-1];
m++;
found(a,b,i-1,j-1,rem,dp);
}
else{
if(dp[i][j]==dp[i-1][j])
found(a,b,i-1,j,rem,dp);
else if (dp[i][j]==dp[i][j-1])
found(a,b,i,j-1,rem,dp);
}
}所以总体的代码为：
#include<iostream>
using namespace std;
#include<algorithm>
#include <cstring>
int m; //m用来记录两个字符串相等的个数
void found(string a,string b,int i,int j,char rem[],int dp[100][100]);
int main()
{
string s1;
string s2;
int i,j;
cout<<"请输入第一个字符串：";
cin>>s1;
cout<<"请输入第二个字符串：";
cin>>s2;
i=s1.length();
j=s2.length();
int dp[i+1][100];
char rem[max(i,j)];
memset(dp,0,sizeof(dp));
for(int p=1;p<=i;p++)
{
for(int q=1;q<=j;q++)
{
if(s1[p-1]==s2[q-1])
{
dp[p][q]=dp[p-1][q-1]+1;
}
else
{
dp[p][q]=max(dp[p-1][q],dp[p][q-1]);
}
}
}
cout<<"最大子序列的个数为："<<dp[i][j]<<endl;
found(s1,s2,i,j,rem,dp);
for(int g=m-1;g>=0;g--) //因为是逆序保存的所以需要逆序输出
{
cout<<rem[g];
}
}
void found(string a,string b,int i,int j,char rem[],int dp[][100]){
if(i==0 ||j==0){
return;
}
if(a[i-1]==b[j-1])
{
rem[m]=a[i-1];
m++;
found(a,b,i-1,j-1,rem,dp);
}
else{
if(dp[i][j]==dp[i-1][j])
found(a,b,i-1,j,rem,dp);
else if (dp[i][j]==dp[i][j-1])
found(a,b,i,j-1,rem,dp);
}
}运行结果案例如下：
文章来源地址https://www.toymoban.com/news/detail-765746.html
文章来源：https://www.toymoban.com/news/detail-765746.html
到了这里，关于C++ 求解最长公共子序列（不仅仅求出其大小）（简单易懂！！！）（动态规划）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
