文档介绍：该【动态规划中的最长公共子序列 】是由【明月清风】上传分享，文档一共【15】页，该文档可以免费在线阅读，需要了解更多关于【动态规划中的最长公共子序列 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2n（包括空）
说“至多”是因为子序列可能相等（但具有不同下标序列）
定义：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。
找出{A, B, C, D}的所有子序列
思考：有n个元素的序列至多有多少个子序列？
01
02
最长公共子序列
01
定义：如果序列Z既是序列X的子序列又是序列Y的子序列，则称Z是X和Y的公共子序列。
02
找出X = (A, B, C, D, A, B), Y = (B, D, C, A, B, A)的所有公共子序列。
公共子序列
找出X和Y的最长公共子序列。
01
本节的问题是只找出一个最长公共子序列。
04
对于任意给定的X和Y，它们的最长公共子序列唯一吗？举例说明。
02
不一定。如{A, B}与{B, A}
03
最长公共子序列
设序列X={x1, x2, …, xm}, Y={y1, y2, …, yn}, Z={z1, z2, …, zk},则
若xm = yn, 则Zk - 1 是Xm – 1和Yn – 1的最长公共子序列；
如：X = {…, C}, Y = {…, C}, 则Z = {…, C}
最长公共子序列的结构
最长公共子序列的结构(续)
若xm ≠ yn, 且zk ≠ xm，则Z是Xm – 1和Y的最长公共子序列；
如：X = {… , C}, Y = {…, B}, zk ≠C, 则在计算最长公共子序列时，可不考虑X的最后一个元素C
1
2
最长公共子序列的结构(续)
若xm ≠ yn, 且zk ≠ yn，则Z是X和Yn– 1的最长公共子序列
如：X = {… , C}, Y = {…, B}, zk ≠B, 则在计算最长公共子序列时，可不考虑Y的最后一个元素B
最长公共子序列的结构(续)
01
两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，因此，最长公共子序列问题具有最优子结构性质。
02
可否根据序列的第1个元素来重述本问题？这样做有什么优缺点？
1
可以。这样做不利于描述，如前面Xm–1可以方便地表示X前m – 1 个元素，改后就比较麻烦。从递归的角度来看，一般也是从后面增减元素。
2
讨论
当xm = yn时，有一个子问题，即 ：找出Xm –1和Yn – 1的最长公共子序列
当xm yn时，有两个子问题，即 (1)找出Xm – 1和Y的最长公共子序列， (2)找出X和Yn – 1的最长公共子序列。而这两个子问题都包含了同一个子问题(Xm– 1, Yn–1) 。 因此，本问题满足子问题重叠性质。
问题分析
01
02
01
令c[i][j]记录Xi和Yj的最长公共子序列的长度，则有
02
i = 0, j = 0
03
c[i][j] = c[i - 1][j - 1] + 1 xi = yj
04
max{c[i][j - 1] , c[i - 1][j] } xi ≠ yj
问题分析(续)