**
解析：
**
此题一共有两个要点：
1.求上述两个最长公共子序列的长度
2.求所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对10^8求余即可
第一个都很好想到，难点在于第二个。下面是对于求最长公共子序列的长度的一个动态规划图：
由此图可以看出，上述两个字符串的最大公共子序列的长度为4
重点：
此图的状态转移方程：
1.当s1[i]=s2[j]时：dp(i,j)=dp(i-1,j-1)+1
2.当s1[i]!=s2[j]并且dp(i-1,j)>=dp(i,j-1)时：dp(i,j)=dp(i-1,j)
3.否则：dp(i,j)=dp(i,j-1)
下面代码==>利用二维数组是求最大公共子序列的长度：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void lec(string s1,string s2){
int m=s1.size();
int n=s2.size();
vector<vector<int>> dp(m+1);
for(int i=0;i<=m;i++){
dp[i].resize(n+1);
}
//转移状态方程
for(int i=0;i<dp.size()-1;i++){
for(int j=0;j<dp[i].size()-1;j++){
if(s1[i]==s2[j]){
dp[i+1][j+1]=dp[i][j]+1;
}else{
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
}
}
}
for(int i=0;i<dp.size();i++){
for(int j=0;j<dp[i].size();j++){
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
cout<<"最长公共子序列为："<<dp[m][n]<<endl;
}
int main(){
string s1,s2;
cin>>s1>>s2;
lec(s1,s2);
return 0;
}
下面代码==>利用两个一维数组是求最大公共子序列的长度：
大家可以试着利用此方法将状态转移图打印出来，下面代码只输出了最后的结果
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void lec(string s1,string s2){
int m=s1.size();
int n=s2.size();
vector<int> isDp(n+1);
for(int i=0;i<m;i++){
vector<int> nextDp(n+1);
for(int j=0;j<m;j++){
if(s1[i]==s2[j]){
nextDp[j+1]=isDp[j]+1;
}else{
nextDp[j+1]=max(nextDp[j],isDp[j+1]);
}
}
isDp=move(nextDp);
}
cout<<"最长公共子序列为："<<isDp[n]<<endl;
}
int main(){
string s1,s2;
cin>>s1>>s2;
lec(s1,s2);
return 0;
}
重点来了——重点来了——重点来了
这也是此题的难点：
求出所有可能出现的最长公共子序列个数
创建一个二维数组 counts
状态转移方程
1.当s1[i]=s2[j]时：counts(i,j)=count(i-1,j-1)
2.当s1[i]!=s2[j]&&dp(i,j)=dp(i-1,j-1)时：counts(i,j)-=counts(i-1,j-1)
3.当dp(i,j)=dp(i-1,j)时：counts(i,j)+=counts(i-1,j)
4.当dp(i,j)=dp(i,j-1)时：counts(i,j)+=counts(i,j-1)
自述
说实话，这部分我现在也没搞太明白，若有大佬有幸看到这篇博客，希望可以留言指点一下，下面我将附上一篇讲解截图，并附上大佬博客链接：
蓝桥杯每日一题-最长公共子序列
下面附上代码：
下面使用两个二维数组实现的
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD=(int)1e8;
void addMod(int& a,int b){
a=(a+b)%MOD;
}
void lec(string s1,string s2){
int m=s1.size();
int n=s2.size();
vector<vector<int>> dp(m+1);
for(int i=0;i<=m;i++){
dp[i].resize(n+1);
}
vector<vector<int>> counts(m+1);
for(int i=0;i<=m;i++){
counts[i].resize(n+1,1);
}
for(int i=0;i<dp.size()-1;i++){
for(int j=0;j<dp[i].size()-1;j++){
if(s1[i]==s2[j]){
dp[i+1][j+1]=dp[i][j]+1;
counts[i+1][j+1]=counts[i][j];
}else{
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
counts[i+1][j+1]=0;
if(dp[i+1][j+1]==dp[i][j]){
addMod(counts[i+1][j+1],-counts[i][j]);
}
}
if(dp[i+1][j+1]==dp[i+1][j]){
addMod(counts[i+1][j+1],counts[i+1][j]);
}
if(dp[i+1][j+1]==dp[i][j+1]){
addMod(counts[i+1][j+1],counts[i][j+1]);
}
}
}
for(int i=0;i<dp.size();i++){
for(int j=0;j<dp[i].size();j++){
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
cout<<"最长公共子序列为："<<dp[m][n]<<endl;
for(int i=0;i<counts.size();i++){
for(int j=0;j<counts[i].size();j++){
cout<<counts[i][j]<<" ";
}
cout<<endl;
}
cout<<"最长公共子序列为："<<counts[m][n]<<endl;
}
int main(){
string s1,s2;
cin>>s1>>s2;
lec(s1,s2);
return 0;
}
运行结果截屏
下面附上本题的AC代码
也就是用四个一维数组实现，实现了空间优化
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const int MOD=(int)1e8;
void addMod(int& a,int b){
a=(a+b)%MOD;
}
void lec(string s1,string s2){
int m=s1.size();
int n=s2.size();
vector<int> isDp(n+1);
vector<int> isCounts(n+1,1);
for(int i=0;i<m;i++){
vector<int> nextDp(n+1);
vector<int> nextCounts(n+1,1);
for(int j=0;j<m;j++){
if(s1[i]==s2[j]){
nextDp[j+1]=isDp[j]+1;
nextCounts[j+1]=isCounts[j];
}else{
nextDp[j+1]=max(nextDp[j],isDp[j+1]);
nextCounts[j+1]=0;
if(nextDp[j+1]==isDp[j]){
addMod(nextCounts[j+1],-isCounts[j]);
}
}
if(nextDp[j+1]==isDp[j+1]){
addMod(nextCounts[j+1],isCounts[j+1]);
}
if(nextDp[j+1]==nextDp[j]){
addMod(nextCounts[j+1],nextCounts[j]);
}
}
isDp=move(nextDp);
isCounts=move(nextCounts);
}
cout<<"最长公共子序列为："<<isDp[n]<<endl;
cout<<"可能出现的最长公共子序列个数:"<<(isCounts[n]+MOD)%MOD<<endl;
}
int main(){
string s1,s2;
cin>>s1>>s2;
lec(s1,s2);
return 0;
}
本章到此就结束了，谢谢看客们光临本博客