第二章、动态规划算法(2.5.3-2.5.4.3)------公共序列问题(下)
目录
2.5.3最长公共前缀问题
2.5.3.1问题
2.5.3.2确定动态规则(DP、状态转移方程)、初始值
2.5.3.3动态规划算法代码实现
2.5.4最短公共超序列(最短公共父序列)
2.5.4.1问题
2.5.4.2确定动态规则(DP、状态转移方程)、初始值
2.5.4.3动态规划算法代码实现
2.5.3最长公共前缀问题
2.5.3.1问题
最长公共前缀(longest common prefix, LCP)，给定两个序列A和B，返回它们起始位置开始的最长的公共连续子序列的长度，这个起始位置开始的最长的公共连续子序列也简称为最长公共前缀，因而也称返回最长公共前缀的长度。
本题要求是从起始位置开始的公共连续子序列，也就是这个公共连续子序列必须是起始位置开始连续的。
前面讲述的最长公共连续子序列(最长公共子串)，只要保证元素的连续即可，本题不仅要元素的连续，而且元素是从起始位置开始的，因而，前者可能有多个连续子序列，后者最多只有一个连续子序列，而且这个连续子序列是从开始位置开始的。可见，本题是最长公共连续子序列(最长公共子串)问题的一种特殊情形
因此，本题的求解是最长公共连续子序列(最长公共子串)的特例，由于只有一种情形，不需要多次比较确定最终的最长子序列，本题的求解相对要简单，只需要增加一个限制在起始位置开始的条件即可。
计算机的序列是指序列的元素在代码中呈现出的顺序与内存存储顺序一致，在计算机中序列是可以通过索引来引用的。在python中字符串、列表、元组都是序列。
子序列是保持原字符串中的顺序，比如：’ ea’是’ eahjkf’的子序列，但’ ae’不是它的子序列，又比如：字符串’ eahjkf’和’ bhfk’，它们的公共最长子序列为’hk’，但不是’ hfk’，因为这种在另一个字符串中的顺序是不同的。
子序列可以是连续的和不连续的，这里的连续是指子序列中的元素在原序列中是不间隔、不间断的，也即在原序列中也是相邻（紧邻）的，这里的连续类似连贯的意思。
2.5.3.2确定动态规则(DP、状态转移方程)、初始值
由于最长公共前缀问题是最长公共连续子序列的特例，本题的分析过程实际类似2.5.2章节最长公共连续子序列(最长公共子串)的分析过程。
(1)直接相关状态
本题是找出序列中最长公共前缀的长度（也即最长公共前缀的元素的个数），实际也是匹配的过程，只是这种匹配强调连续的单个元素的匹配，每连续匹配成功，长度会累计增加。在这个匹配的循环遍历过程中，本题要求公共连续子序列必须是起始位置开始连续的，因而我们只需要判断序列起始位置的连续匹配情况，求出从起始位置开始，连续匹配成功的元素个数，也就是最长公共前缀的长度。一旦出现不匹配，表示连续匹配终止了，也不用再继续匹配了。在这个匹配过程中，当前状态值受能确保连续性特点的状态的影响。
这里我们以A和B两个字符串为例来求解最长公共前缀，不妨记A=’xcxrcf’，B=’hxrpgf’。
Python的切片是左闭右开的，因而，A[0:i]不包含A[i]、B[0:j]不包含B[j]，下面阅读时注意这一点。
A[0:i]表示字符串A的前i个字符构成的局部字符串，B[0:j] 表示字符串B的前j个字符构成的局部字符串。在计算过程中i，j是随着循环而取值的，我们可以记dp[i][j]是A[0:i]与B[0:j]匹配到的最长公共前缀的长度(个数)，当前状态ij的值由相邻状态i-1j-1的值决定，因为状态转移是通过匹配来实现的，而且从状态i-1j-1到状态ij确保了连续元素（这里连续的概念同上）的匹配特点，也即从A[0:i-1]、B[0:j-1]到A[0:i]、B[0:j]，A、B都同时增加了一个元素，这正好符合A、B对应连续元素的变化，而从状态ij-1到状态ij，是A[0:i]、B[0:j-1]到A[0:i]、B[0:j]，只有B增加了一个元素，A没有增加，不能保证A、B的元素个数同时增加一个，也就不能确保A、B对应连续元素的变化，一个的元素个数不变，一个的元素个数增加，这不能确保连续匹配，连续匹配应该是在上一个状态的基础上，A、B同时增加一个元素，同理，状态i-1j到状态ij也一样。
因此，在当前状态ij的相邻状态i-1j-1、ij-1、i-1j中，要确保匹配到A和B中的连续字符，dp[i][j]受dp[i-1][j-1]影响，当前状态ij的直接相关状态为状态i-1j-1，当前状态ij与ij-1、i-1j没有关系。
此外，本题要求公共连续子序列必须是起始位置开始连续的，因而，在匹配时要确保i与j是相等的，并且当首次遇到不匹配时，终止循环匹配，通过这种条件限定即可实现从起始位置开始的连续匹配，并确定最长公共前缀。
本题的求解类似2.5.2.1最长公共连续子序列(最长公共子串)问题，但本题要确保从起始位置开始的连续，因此，需要再增加限定条件。
(2)当前状态值的确定
状态与状态值是不能等同的，状态是一种定性的描述，状态值是问题所要求的一种定量的衡量。并不是所有的直接相关状态都参与确定当前状态值，当前状态值的唯一性确定还可能与状态转移的因素的作用、求解问题的要求、问题自身的规律特点有关。
下面讨论在不同情形下的状态转移，当前状态ij的状态值dp[i][j]是如何确定的。
①当B[j-1]等于A[i-1]时的状态转移
B[j-1]是字符串B[0:j]的末尾字符，A[i-1]是字符串A[0:i]的末尾字符，由于B[j-1]等于A[i-1]， B[0:j]与A[0:i]的最后一个字符能对应匹配，因而，B[0:j]与A[0:i]匹配到元素的最多个数是B[0:j-1]与A[0:i-1] 匹配到元素的最多个数再加1，也即当前状态值dp[i][j]由dp[i-1][j-1]决定了，即dp[i][j]= dp[i-1][j-1]+1。
因为ij状态的末尾元素能匹配成功(B[j-1]等于A[i-1])，因而B[0:j]与A[0:i]的匹配情况由B[0:j-1]与A[0:i-1] 的匹配情况决定，状态值dp[i][j] 由dp[i-1][j-1]决定了，而且，由上面分析可知，能保证A、B连续个元素匹配。
另外，要确保从起始位置开始的连续，还需要增加i等于j的条件，以确定B[j-1]等于A[i-1]时的状态转移。i等于j的条件可以确保从序列起始位置开始，排除了连续匹配以序列其它位置为开始的情形。
②当B[j-1]不等于A[i-1]时的状态转移
由于B[j-1]不等于A[i-1]，此时，到达ij状态的末尾字符不匹配，出现了不匹配，可以理解为ij状态与状态i-1j-1中断了连续的关系，或不存在连续个匹配。根据上面的分析可知，要保证连续匹配，ij与ij-1、i-1j也没有关系。因此，此时，表示公共前缀结束或没有公共前缀，需要终止循环匹配，此时可以不求dp的元素值，此时值没实际意义了。
同样，要确保从起始位置开始的连续，还需要增加i等于j的条件，以确定B[j-1]不等于A[i-1]时的状态转移。i等于j的条件可以确保从序列起始位置开始，排除了连续匹配以序列其它位置为开始的情形。
(3)动态规则(DP、状态转移方程)
上面的描述可以表示为下面的动态规则(DP、状态转移方程):
因为前面匹配后的下一步就到当前状态，所以当前状态dp[i][j]值是与相邻的状态有关的，考虑到连续个元素匹配，dp[i][j]值只由i-1j-1直接相关状态转化而来。上面的描述内容也即是普通情况下的动态规则DP，根据这个DP，我们可以计算出新的状态值。
在动态规划算法的两层循环中，外层循环是i，内层循环是j，i、 j与A、B字符串的索引对应，在状态方程中状态之间的关系能体现出匹配关系，在两层循环中，外层循环运行一个i，内层循环j遍历一遍。
(4)初始值
下面我们再来确定初始状态。
初始状态的源头是空字符，若A是空字符，B为非空的字符串，这时匹配个数都为0。若A是非空的字符串，B为空字符，这时匹配个数也都为0。A是空字符，B为空字符，本题是考虑子序列的元素个数，空字符与空字符可以不考虑匹配，不妨记dp[0][0]=0，这有利于上面动态规则(DP、状态转移方程)的计算。
前面我们是从字符串A、B都不为空进行分析，dp[i][j]的索引与字符串的索引是一致的，这种不影响分析，但现在加上刚才增加了空字符这种初始状态，要注意dp[i][j]的索引变成比字符串的索引多一个，如图2-23所示。因此，在代码中注意i、j索引表达的变化，否则，使用不当容易产生异常提示string index out of range。
2.5.3.3动态规划算法代码实现
上面的分析及下面代码的实现可以结合下面图2-23来理解。浅红色方框的状态与浅蓝色方框的状态有关。
图2-23 最长公共前缀
(1)完整代码
下面程序代码是求解最长公共前缀问题，函数longest_common_prefix_subsequence_length ()采用动态规划求解最长公共前缀的长度，是按上述分析过程实现的，完全体现了我们上面对动态规划的论述，从代码中就能看到动态规划算法的思想，我们可以结合下面代码来理解动态规划算法在本问题中的应用。
代码中函数find_LCPS_dynamic ()采用动态规划求解最长公共前缀。下面代码中是以字符串序列为例，若是数字型序列，在初始化或存储操作时应该做相应改变以适合数字型的操作特点（比如：在python中用列表存储数字序列，可以用方法append()），其他是一样的。
#A,B为序列,比如:python中的字符串,列表等。
#最长公共前缀。
def longest_common_prefix_subsequence_length(A, B):
#增加1,因为初始值增加了空字符有关的行列。
n, m = len(A) + 1, len(B) + 1
#生成一个二层列表,存放状态值。
dp = [[0] * m for i in range(n)]
#动态规划的初始值,一般来讲,在匹配时空字符不参与匹配,
#因而空字符作为初始状态,状态值为0,上面已经初始化,下面可以省去。
#for i in range(1, n): #空字符的处理
#dp[i][0] = 0
#for j in range(1, m): #空字符的处理
#dp[0][j] = 0
#初始化,便于下面存储和比较最长公共子串的长度大小。
max_length = 0
#下面使用变量flag的值来判断跳出外循环,也可以用python的for else语句。
#下面find_LCPS_dynamic()函数采用了for else语句。
flag=0
#下面为当前状态值由之前直接相关状态决定,具体含义参见文档中的分析过程。
#这里的i,j索引是dp的索引,0表示初始状态的空字符,因此,索引从1开始。
for i in range(1, n):
for j in range(1, m):
#下面要注意A、B的索引值,它们的索引不是dp对应的索引值,要减去1,
#才刚好对应,因为dp增加了一行一列。
#i==j可以确保从序列起始位置开始,排除了连续匹配以序列其它位置为开始的情形。
#相等时,当前状态由i-1j-1状态决定。
if i==j and A[i - 1] == B[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
max_length=dp[i][j]
elif i==j and A[i - 1] != B[j - 1]:
#不相等时,出现了不匹配,可以理解为连续个匹配中断,或不存在连续个匹配,
#此时dp的元素值默认为0,表示此时最长公共前缀长度为0,不属于最长公共前缀。
#由于初始化为0,因而此时默认这个值,
#但本题要求的是前缀,出现这种情况,表示前缀结束或没有前缀,下面会跳出循环,
#因而此时可以不求dp的元素值,此时值没实际意义了。
flag=1
break
if flag:
break
print('dp逐行输出：')
for i in range(n):
print(dp[i])
return max_length
#采用动态规划来求解最长公共前缀。
def find_LCPS_dynamic(A,B):
#增加1,因为初始值增加了空字符有关的行列。
n, m = len(A) + 1, len(B) + 1
#生成一个二层列表,存放状态值。由于前缀只有一个,初始化的初始值用空字符'',
#不用列表[''],在求最长公共连续子序列时我们用列表['']以便存放多个最长公共连续子序列。
dp1 = [[''] * m for i in range(n)]
#动态规划的初始值,一般来讲,在匹配时空字符不参与匹配,
#因而空字符作为初始状态,为便于计算,状态值记为'',上面已经初始化,下面可以省去。
#for i in range(1, n): #空字符的处理
#dp[i][0] = ''
#for j in range(1, m): #空字符的处理
#dp[0][j] = ''
#初始化,便于下面存储最长公共前缀。
max_prefix = []
#这里的i,j索引是dp1的索引,0表示初始状态的空字符,因此,索引从1开始。
for i in range(1,n):
for j in range(1,m):
#下面要注意A、B的索引值,它们的索引不是dp对应的索引值,要减去1,才刚好对应,
#因为dp增加了空字符处理的行和列,dp的行和列要多1个。
#所以A[i - 1],B[j - 1]刚好是对应了当前状态dp[i][j]
#出现相同值,也即匹配到时,由dp1[i-1][j-1]决定。
#i==j可以确保从序列起始位置开始,排除了连续匹配以序列其它位置为开始的情形。
#下面是从起始位置开始连续个元素匹配,也即最长公共前缀的判断。
if i==j and A[i -本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！