最长公共子序列问题入门-白红宇

最长公共子序列问题入门

阅读量：3898 次

发布时间：2019-05-23

本文共 966 字，大约阅读时间需要 3 分钟。

这也是一道关于动态规划比较经典的题目，也就是将原问题分成一个个子问题，

用一个二维数组 dp[i][j]表示S1字符串中前i个字符和S2字符串中前j个字符分别组成的最长公共子序列，而其中就等于 max(dp[i-1][j],dp[i][j-1]),再加上默认值 dp[o][j]=0和dp[i][0]=0.

问题就是：

（首先要知道，这里的子序列不一定是连续的，只要是一部分的就行。）

然后需要搞清楚，对于s1[x]和s2[y]这两种的最后一个值相不相同的情况做一个区分，如果最后一个是相同的话，那么一定是 dp[x-1][y-1]+1 也就是加上最后一个数组，如果s1[X]和S2[Y]的最后一个不相同的话，需要知道，就是dp[x[[y[=max(dp[x-1][y],dp[x][y-1])中的一个

刚开始没有初始化dp，所以绕了一点弯路

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;//最长公共子序列int main(){ char Str1[20]; char Str2[20]; //先输入他们对应的值 scanf("%s%s",Str1,Str2); //再求他们的长度 int le1=strlen(Str1)-1; int le2=strlen(Str2)-1; // printf("%d %d",le1,le2); //再创建一个求最长子序列的二维数组 int dp[20][20]={ 0}; //再初始化 dp[0][le2]=0; dp[le1][0]=0;//当其中有一个是0的时候，那么最长子序列一定是0 //再开始遍历 for(int i=1;i<=le1;i++) for(int j=1;j<=le2;j++){ if(Str1[i]==Str2[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } printf("%d",dp[le1][le2]);}

转载地址：http://jyfen.baihongyu.com/

你可能感兴趣的文章