算法设计与分析学习笔记——最长公共子序列

最长公共子问题

待解决问题：

    给定两个序列Ｘ和Ｙ，求其一个最长公共的序列Ｚ。

    补充解释：X(m)={x1, x2,,,,,xm}，Ｙ(n)={y1, y2,,,,,yn}，Ｘ和Ｙ可以有共同的元素，Ｚ是这些共同元素的集合，其元素顺序在ＸＹＺ中都是升序排序的（Z中元素的顺序不能在X,Y中出现前后颠倒的情况）。

    例子：X={A, B, C, B, D, A, B}，Y={B, D, C, A, B, A}，那么序列{B, C, B, A}是Ｘ和Ｙ的最长公共子序列。{B, C, A}也是Ｘ和Ｙ的子序列，但它不是最长的。

穷举法

        最常见的方法就是穷举法，它的思路是：分别列举出Ｘ和Ｙ的所有序列，接着比较Ｘ和Ｙ的所有子序列，选择公共序列，最后选择长度最长的公共序列，这个公共序列就是我们要求的最长公共子序列。

    

子结构分析：

        我们发现，如果X和Y的长度都很短（假设长度都为1），我们很容易得出最优解，但是事实往往是很残酷的。如果给定一组长度很长的X,Y，我们利用分治策略的思路，能不能从X和Y的子段中一步一步得出答案呢？

        分治策略和动态规划第一步都需要刻画最优解的结构。下面先来看一下最长公共子序列最优解的结构。

        假设X(m) = {x1, x2.....xm} 和 Y(n) = {y1, y2....yn}的最长公共子序列为Z = {z1, z2....zk}，现在考虑一下X(m-1)和Y(n-1)的最优解和Z之间的关系。

            1.如果X和Y的最后一个元素相等，并且等于Z的最后一个元素，那么说明Z(k-1)是X(m-1)和Y(n-1)的公共子序列

            2.如果xm != yn，并且xm和yn也不等于zk，那么，Z是X(m-1)和Y(n-1)的公共子序列

            3.如果xm != yn，zk = xm ！= yn，那么Z是X(m)Y(n-1)的最长公共子序列

            4.如果xm != yn，zk = yn ！= xm，那么Z是X(m-1)Y(n)的最长公共子序列

        在分析了X(m),Y(n)的解的结构之后，再于x(m-1),y(n-1)的解结构作对比，我们可以发现：Ｚ被分类到以上三种情况的哪一种，主要取决于X,Y的最后一个元素是否相等，所以我们可以归纳出一个递归函数：

            定义：c[i][j]为X(i)和Y(j)的最长公共序列(i <= m, j <= n)

            判断退出递归条件：如果 i 和 j 有一个等于０，可以立即得出并返回结果：当前两个子序列的最长公共子序列长度为０。

            比对当前X,Y的最后一个元素。

                如果Xi = Yj，那么返回结果：c[i][j] = c[i -1 ][j - 1] + 1

                如果Xi != Yj，那么返回结果：max{ c[i][j - 1], c[i - 1][j] }

        在这个递归函数里，我们每次在求c[i][j]的时候，需要使用c[i-1][j-1]等形式的值，我们一开始是不知道的。例如现在我们要求c[5][4]，我在这层函数里发现需要使用c[4][4]的值，我现在不知道，怎么办呢？我们只需要创建一个同样的函数，并且把(4, 4)这两个参数送给它就行了，同样，这个新函数也可能不会直接知道c[4][3]的值，这个新函数可以再创建个同样的函数，把(4, 3)送进去就行了....直到再创建的函数遇到了退出递归的条件，并且向上返回了0这个值。上一层函数拿到这个0值做一次处理之后再向上返回到上一层函数....

动态规划

        代码如下

        

求解例题c[7][6，]矩阵构造方法及过程

    1.把序列分别按横向和竖向填入矩阵的第一行和第一列

    2.比对第一行和第一列单元格所对应的两个字母(黄色区域)，字母不同填入前面（或者上面）的数字，字母相同则填入（前面的数字+1），但不得超过这个单元格的行数和列数最小的那一个。

    3.依次按行或按列填入数字。如果单元格对应的字母不同，填入这个单元格正上方和正前方最大的那一个；如果字母相同，填入（这个单元格正上方和正前方最大的数+1），但不得超过行数和列数最小值。

最优解还原

      从矩阵右下角开始往左上角寻找+1的记录，例题矩阵中被涂成了红色。每寻找到一个+1的单元格，记录对应的字母并且删除该单元格右方和下方所有的单元格。此题有两个解，分别是{B，C，A，B}和{B，C,  B, A}