最长公共子序列，典型的动态规划，时间复杂度O(mn)，空间复杂度O(mn),

如果只要长度，不要序列，优化时间复杂度O(mn),空间复杂度用两行min（O(m)，O(n)）

代码如下：

1 #include 
     
       2 using namespace std; 3 #include 
      
        4  5 void lcs(int **A,const string &x,const string &y) 6 { 7     int m=x.size(); 8     int n=y.size(); 9     if(m<=0||n<=0)10         return;11     for(int i=0;i<=n;i++)           //A[m+1][n+1] 都是从0到m和0到n12         A[0][i]=0;13     for(int i=1;i<=m;i++)14         A[i][0]=0;15     for(int i=1;i<=m;i++)16         for(int j=1;j<=n;j++)17         {18             if(x[i-1]==y[j-1])            //注意，因为字符串是从0到m-1和0到n-119                 A[i][j]=A[i-1][j-1]+1;20             else21                 A[i][j]=max(A[i-1][j],A[i][j-1]);22         }23 }24 25 void print(int **A,int m,int n,const string &x,const string &y)26 {27     if(m==0||n==0)28         return;29 30     if(x[m-1]==y[n-1])              //必须用递归，不然是倒序的，从A[m][n]开始向前31     {32         print(A,m-1,n-1,x,y);33         cout<
       
        <
        
         =A[m][n-1])36         print(A,m-1,n,x,y);37     else38         print(A,m,n-1,x,y);39 }40 41 int main()42 {43     string x="abcdefglasfsd";44     string y="abegsdfa";45     int m=x.size();46     int n=y.size();47     int **A=new int*[m+1];48     for(int i=0;i<=m;i++)49         A[i]=new int[n+1];50     lcs(A,x,y);51     print(A,m,n,x,y);52     for(int i=0;i<=m;i++)53         free(A[i]);54     free(A);55     system("PAUSE");56 }
        
       
      
     

主要注意下标问题，A[m+1][n+1]和字符数组是0~m-1和0~n-1。

（2）还用中矩阵解法，实在搞不定。