最长公共子序列

一，问题描述

给定两个字符串，求解这两个字符串的最长公共子序列（最长公共序列）比如字符串1：BDCABA;字符串2：ABCBDAB

则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA

二，算法求解

这是一个动态规划的题目对于可用动态规划求解的问题，一般有两个特征：①最优子结构;②重叠子问题

①最优子结构

设X =（x1，x2，… xn）和Y = {y1，y2，… ym}是两个序列，将X和Y的最长公共子序列记为LCS（X ，Y）

找出LCS（X，Y）就是一个最优化问题。因为，我们需要找到X和ý中最长的那个公共子序列。而要找X和ÿ的LCS，首先考虑X的最后一个元素和ÿ的最后一个元素。

1）如果xn = ym，即X的最后一个元素与Y的最后一个元素相同，这说明该元素一定位于公共子序列中。因此，现在只需要找：LCS（Xn-1，Ym-1）

LCS（XN-1，YM-1）就是原问题的一个子问题。为什么叫子问题？因为它的规模比原问题小。（小一个元素也是小嘛…）

为什么是最优的子问题？因为我们要找的是XN-1和YM-1的最长公共子序列啊…最长的！换句话说，就是最优的那个。（这里的最优就是最长的意思）

2）如果xn！= ym，这下要麻烦一点，因为它产生了两个子问题：LCS（Xn-1，Ym）和LCS（Xn，Ym-1）

因为序列X和序列ý的最后一个元素不相等嘛，说明那一个求最后元素不可能的英文最长公共子序列中的元素嘛。（都不相等了，怎么公共嘛）。

LCS（Xn-1，Ym）表示：最长公共序列可以在（x1，x2，… x（n-1））和（y1，y2，… yn）中找。

LCS（Xn，Ym-1）表示：最长公共序列可以在（x1，x2，… xn）和（y1，y2，… y（n-1））中找。

求解上面两个子问题，得到的公共子序列谁最长，那谁就是LCS（X，Y）用数学表示就是：

LCS = MAX {LCS（XN-1，YM），LCS（XN，YM-1）}

由于条件1）和2）考虑到了所有可能的情况。因此，我们成功地把原问题转化成了三个规模更小的子问题。

②重叠子问题

重叠子问题是啥？就是说原问题转化成子问题后，子问题中有相同​​的问题。咦？我怎么没有发现上面的三个子问题中有相同​​的啊???

好的，来看看，原问题是：LCS（X，Y）子问题有❶LCS（XN-1，YM-1）❷LCS（XN-1，YM）❸LCS（XN，YM-1）

初一看，这三个子问题是不重叠的可本质上它们是重叠的，因为它们只重叠了一大部分举例：

第二个子问题：LCS（XN-1，YM）就包含了：问题❶LCS（XN-1，YM-1），为什么？

因为，当XN-1和YM的最后一个元素不相同时，我们又需要将LCS（XN-1，YM）进行分解：分解成：LCS（XN-1，YM-1）和LCS（XN-2 ），YM）

也就是说：子在问题的继续分解中，有些问题是重叠的。

由于像LCS这样的问题，它具有重叠子问题的性质，因此：用递归来求解就太不划算了因为采用递归，它重复地求解了子问题，所有子问题加起来的个数可是指数级的哦…

关键是采用动态规划时，并不需要去一一计算那些重叠了的子问题或者说：用了动态规划之后，有些子问题是通过“查表”直接得到的.
公式如下:

赋初值:

这里要将i=0或者j=0即没有数字或字母的地方赋值为0.如果是字符串,为0时可能有相同的字母可用

 char a[1000],b[1000];
 scanf("%s %s",a,b);
        x=strlen(a);
        y=strlen(b);
 for(int i=0;i<=x;i++)
         {
             for(int j=0;j<=y;j++)
             {
                 if(i==0||j==0)  
                    dp[i][j]=0;
                 else if(a[i-1]==b[j-1])  //字母下标-1,实现字符串a从1-x存在,字符串b从1-y存在.
                     dp[i][j]=dp[i-1][j-1]+1;
                 else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

             }
         }

---

原文：https://blog.****.net/qq_36770641/article/details/81463895