动态规划解最长公共子序列(LCS)原理及模板-阿里云开发者社区

动态规划解最长公共子序列(LCS)原理及模板

2024-01-11 24

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 动态规划解最长公共子序列(LCS)原理及模板

最长公共子序列

1.LCS的概念

（1）递增（2）可以连续可以不连续（3）公共：在S1内，又在S2内（4）最长：5（acdEH）>4(acdE)…

2.LCS的规律

下列图片来自动态规划解最长公共子序列(LCS)(附详细填表过程)

看了下面6张图，就可以得出上图的结论，从而递推出

if(s1[i-1]==s2[j-1])
    dp[i][j]=dp[i-1][j-1]+1;
else
    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

最长公共子序列的模板

1.动态规划求解LCS模板

#include<iostream>
#include<algorithm>
using namespace std;
int dp[1005][1005];
int main() {
  string s1,s2;
  while(cin>>s1>>s2) {
    int l1=s1.size();
    int l2=s2.size();
    for(int i=0; i<=l1; i++) {
      dp[0][i]=0;
      dp[i][0]=0;
    }
    for(int i=1; i<=l1; i++) {
      for(int j=1; j<=l2; j++) {
        if(s1[i-1]==s2[j-1])
          dp[i][j]=dp[i-1][j-1]+1;
        else
          dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      }
    }
    cout<<dp[l1][l2]<<endl;
  }
}

2. LCS字符串输出(还原)

看23-39行，1-23行代码是LCS长度的代码

#include<iostream>
#include<algorithm>
using namespace std;
int dp[1005][1005];
int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        int l1=s1.size();
        int l2=s2.size();
        for(int i=0;i<=l1;i++){
            dp[0][i]=0;
            dp[i][0]=0;
        }
        for(int i=1;i<=l1;i++){
            for(int j=1;j<=l2;j++){
                if(s1[i-1]==s2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        cout<<dp[l1][l2]<<endl;
        int i=l1,j=l2,z=0;
        string s3;
    while(i!=0 && j!=0){
      if(s1[i-1]==s2[j-1]){
        i--;
        j--;
        s3[z++]=s1[i];
      }
      else if(dp[i-1][j]<dp[i][j-1]){
        j--;
      }
      else if(dp[i-1][j]>=dp[i][j-1]){
        i--;
      }
    } 
    for(int i=z-1;i>=0;i--){
      cout<<s3[i];
    }
    cout<<endl;
    }
}