正文之前

囚徒健身初期感觉还是很温和的，练习起来不吃力，而且对身体的负荷也很小，还是不错的，推荐大家也学习下。。进入正题，最长公共子序列问题

正文

• （1）子序列： 一个序列A ＝ a1,a2,……an,中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。例如 : 对序列1,3,5,4,2,6,8,7来说，序列3,4,8,7 是它的一个子序列。
  对于一个长度为n的序列，它一共有2^n 个子序列，有(2^n – 1)个非空子序列。

请注意：子序列不是子集，它和原始序列的元素顺序是相关的。

• （2）公共子序列 ： 顾名思义，如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。

• （3）最长公共子序列
  A和B的公共子序列中长度最长的（包含元素最多的）叫做A和B的公共子序列。仍然用序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5. 它们的最长公共子序列是：

1,4,8,7
1,4,6,7

最长公共子序列的长度是4 。
请注意: 最长公共子序列不唯一。

以上基础内容介绍来自CSDN博客：动态规划基础篇之最长公共子序列问题

那么，根据算法导论的内容，我们要定义一个子序列的表达形式：

定义包含一个序列 X 前i个元素的子序列为Xi

那么根据最优子结构的定理：

• 也就是说，如果两个序列的最后一个元素相等，那么这个结尾元素一定是他们的最长公共子序列的最后一个元素，没毛病对不？？？这就是第一点的内容。

• 那么如果结尾元素不相等，则对其中一个序列查看结尾元素，如果它不等于最长子序列的最后一个元素，那么丢弃掉这个序列的最后一个元素也玩不影响我们的最长公共子序列的求解过程。这个时候就可以直接考虑该序列的倒数第二个元素，。。也就是第二点的内容。

• 同理，如果考察的序列结尾元素不相等，考察的第一个序列的结尾元素等于最长子序列的结尾元素，那么肯定丢弃掉另外一个序列的结尾元素是毫无影响的，对不对？第三点的内容了。。

原文

根据这个思想。我们可以得到下面的代码，具体的思路建议大家直接参考《算法导论》这一本神书来理解。当然，看代码能理解就最好了。。要我慢慢解释是不可能的。。。我必须回去睡午觉了。。你们看看时间：

#include <iostream>
#include<string>

using namespace std;

string Y = "BDCABA";
string X = "ABCBDAB";

string b[8][7];

int c[8][7];

void LCS(int m, int n ){

    for (int i = 0; i <=m; ++i)
    {
        c[i][0] = 0;
    }
    for (int i = 0; i < n+1; ++i)
    {
        c[0][i] = 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] = "LT";
            }
            else if (c[i-1][j] >= c[i][j-1])
            {
                b[i][j] = "TOP";
                c[i][j] = c[i-1][j];
            }
            else
            {
                b[i][j] = "LEFT";
                c[i][j] = c[i][j-1];
            }
        }
    }
}


void printLCS(string b[8][7],string X,int i,int j){
    if (i==0 || j==0)
    {
        return;
    }
    if (b[i][j] == "LT")
    {
        printLCS(b,X,i-1,j-1);
        cout<<Y[j-1]<<endl;
        // cout<<X[i-1]<<endl;
    }
    else if (b[i][j] == "TOP")
    {
        printLCS(b,X,i-1,j);
    }
    else
        printLCS(b,X,i,j-1);
}


int main(int argc, char const *argv[])
{
    int m = X.size();
    int n = Y.size();
    LCS(m,n);
    printLCS(b,X,m,n);
    return 0;
}

之所以要设置两个数组的长度比XY这两个字符串的长度+1 是因为要存储一个初始位0 啊，，，b数组其实可以不+1的，但是为了i,j方面的统一，我还是直接多开一点吧。。反正没影响不是？

下面是运行结果（Output）：

正文之后

溜了溜了。晚上还要去武昌火车站接人。。得亏是晚上。。。不然晒死。。。