最长公共子序列.cpp

求出任意两个序列的最长公共子序列,使用了动态规划的方法

#include <iostream>
#include <string>
using namespace std;

int main()
{
     int n,m,len1,len2,**c,i,j;
     char *a,*b;
     cout<<"请分别输入两个序列的长度:"<<endl;
     cin>>n>>m;
     a=new char[n];
     b=new char[m];
     cout<<"请分别输入两个序列:"<<endl;
     cin>>a>>b;
     c=new int*[n+1];
     for(i=0;i<=n;i++)
     c[i]=new int[m+1];
     
     for(i=1;i<=n;i++)
     c[i][0]=0;
     for(i=0;i<=m;i++)
     c[0][i]=0;
     
      
      for(i=0;i<n;i++)
      for(j=0;j<m;j++)
      {
          if(a[i]==b[j])
          c[i+1][j+1]=c[i][j]+1;
          else
          {
              if(c[i][j+1]>c[i+1][j])
              c[i+1][j+1]=c[i][j+1];
              else
              c[i+1][j+1]=c[i+1][j];
              }            
                      }
      cout<<"最长的公共子序列含有"<<c[n][m]<<"个"<<endl;                
      system("pause");
      return 0;
    }