# # 1 问题定义 > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207124139234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > 子序列的含义是 Z 中的所有元素都按照顺序出现在 X 中，此处的按照顺序不要求必须连续，只要先后出现的顺序没有改变即可。 > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207124314381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207124539350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207124653494.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) # 2 问题分析 > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/2020120712473697.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/2020120716203311.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > 从后往前推，如果两个序列中的最后一元素相等，则这个元素一定在最长公共子序列中 > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/2020120712562924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > **当 Xm!=Yn 且 Zk!=Xm 时，Zk 和 Yn 的关系有两种，即相等，或者不相等；例 4 为相等的例子；下一页的例 5 为不相等的例子** > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207162252449.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207162407592.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > **当 Xm!=Yn 且 Zk!=Ym 时，Zk 和 Xm 的关系有两种，即相等，或者不相等；例 6 为相等的例子；下一页的例 7 为不相等的例子。** > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207162754553.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/2020120716290411.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) # 4 子问题的递归结构 > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207163056152.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207163121427.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207163608471.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207164202563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207164240805.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207164257987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) # 5 核心代码 ```cpp void LCS_LENGTH(int m, int n, char *x, char *y, int **c, int**b) { int i,j; for (i=1; i<=m; i++) //初始化第一列 c[i,0]=0; for (j=1; j<=n; j++) //初始化第一行 c[0,j]=0; //填表，一行一行地构造表 for (i=1; i<=m; i++) //对应x for (j=0; j<=n; j++) //对应y if (x[i]==y[j]) //判断最后一个元素是否相等 { 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"; } } //计算复杂性：O(mn) ``` # 6 构造最长公共子序列 ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207170154295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207170208916.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207170244632.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207170313954.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) 核心代码： ```cpp void LCS(int i, int j, char *x, int **b) { if (i==0 || j==0) return; if (b[i,j]=="1" ) { LCS(i-1, j-1, x, b); cout < 1 构造表，并初始化 > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/2020120717153796.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207171609495.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > **C[1][1]=max{c[0][1],c[1][0]}={0,0}=0,此时，b[1][1]=2 或 3 都可以，不影响最终的结果。** > 最终构造出的表为 > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207173901870.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > 根据表构造解 > 该表的使用方法是： > 在 c 表中从最右下角的那个元素 c[7][6]开始，看 b 表中对应位置 b[6][7]的值，如果为 1，则在 c 表中从当前位置往左上角走；如果为 2，则在 c 表中从当前位置往正上方走；如果为 3，则在 c 表中从当前位置沿水平方向往后退一位；依次类推，直到 c 表中箭头退到 c[0][0]为止。
> 左上方箭头对应两个元素：头部元素和尾部元素；其中每个左上方箭头的**尾部元素**为公共子序列的一个元素（原因：b[i][j]=1 的定义），把这些元素和在一起即为要求的公共子序列。
> **水平角度看** 左上方箭头对应的尾部元素编号为 2， 3， 4， 6，它们分别对应 X 序列中的 B C B A
> **垂直角度看**，左上方箭头对应的尾部元素编号为 1， 3， 5， 6，它们分别对应 X 序列中的 B C B A
> ==这两种方法是等价的== > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207174734199.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70) > ![在这里插入图片描述](https://blog-1306207361.cos.ap-guangzhou.myqcloud.com/blog/20201207174753492.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTA0OTMw,size_16,color_FFFFFF,t_70)

动态规划