问题描述：

    给定两个序列 X=<x1, x2, ..., xm>, Y<y1, y2, ..., yn>，求X和Y长度最长的公共子序列。(子序列中的字符不要求连续)

 

   这道题可以用动态规划解决。定义c[i, j]表示Xi和Yj的LCS的长度，可得如下公式：

伪代码如下：

C++实现：

int longestCommonSubsequence(string x, string y){    int m = x.length();    int n = y.length();    vector< vector
     
       > c(m + 1, vector
      
       (n + 1));    for (int i = 0; i <= m; ++i)        c[i][0] = 0;    for (int j = 1; j <= n; ++j)        c[0][j] = 0;    for (int i = 1; i <= m; ++i)    {        for (int j = 1; j <= n; ++j)        {            if (x[i-1] == y[j-1])                c[i][j] = c[i-1][j-1] + 1;            else if (c[i-1][j] >= c[i][j-1])                c[i][j] = c[i-1][j];            else                c[i][j] = c[i][j-1];        }    }    return c[m][n];}
      
     

后记：

我本来以为我已经掌握了LCS，其实不过是记住了LCS的状态转移方程。15号参加了创新工场2016校园招聘笔试，题目要求打印出LCS，我就懵逼了。其实《算法导论》里讲的清清楚楚啊。

 

贴一下我的C++实现：

vector< vector
     
       > b;    //辅助数组void LCS(string x, string y){    int m = x.length();    int n = y.length();    vector< vector
      
        > c(m + 1, vector
       
        (n + 1));    for (int i = 0; i <= m; ++i)        c[i][0] = 0;    for (int j = 1; j <= n; ++j)        c[0][j] = 0;    b.resize(m+1);    for (int i = 1; i <= m; i++)    {        b[i].resize(n+1);    }    for (int i = 1; i <= m; i++)        for (int j = 1; j <= n; j++)        {            b[i][j] = 0;        }    for (int i = 1; i <= m; ++i)    {        for (int j = 1; j <= n; ++j)        {            if (x[i-1] == y[j-1])            {                c[i][j] = c[i-1][j-1] + 1;                b[i][j] = 1;    //            }            else if (c[i-1][j] >= c[i][j-1])            {                c[i][j] = c[i-1][j];                b[i][j] = 2;   //            }            else            {                c[i][j] = c[i][j-1];                b[i][j] = 3;   //            }        }    }}void printLCS(vector< vector
        
          > &b, string x, int i, int j){    if (i == 0 || j == 0)        return ;    if (b[i][j] == 1)    {        printLCS(b, x, i-1, j-1);        printf("%c", x[i-1]);    }    else if (b[i][j] == 2)        printLCS(b, x, i-1, j);    else        printLCS(b, x, i, j-1);    }
        
       
      
     

阿里、腾讯、创新工场全部笔试跪；网易互联网简历挂；明天去面百度和华为，加油！！！