转载

动态规划之最长公共子序列(LCS)

最长公共子序列(LCS,Longest Common Subsequence)。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。

设X(m)={x(1), x(2), x(3),....,x(m)} 和 Y(n)={y(1), y(2), y(3),....,y(n)}的最长公共子序列Z(k)={z(1), z(2),z(3),....,z(k)}

首先，将原问题分解为子问题，得出一个已知的结论：当m或n等于0时，k等于0，即公共子序列长度为0

当m和n都不等于0时，此时分为三种情况：

(1) x(m) == y(n) ，此时z(k) = x(m) = y(n)，该元素属于当前最长公共子序列的最后一个元素。此时Z(k-1)={ X(m-1)与Y(n-1)的最长公共子序列 }

(2) x(m) ！= y(n) ，且z(k) ！= x(m)，此时Z={ X(m-1)与Y(n)的最长公共子序列 }

(3) x(m) ！= y(n) ，且z(k) ！= y(n)，此时Z={ X(m)与Y(n-1)的最长公共子序列 }

其中X(m-1)={x(1), x(2), x(3),....,x(m-1)} ， Y(n-1)={y(1), y(2), y(3),....,y(n-1)}，Z(k-1)={z(1), z(2),z(3),....,z(k-1)}

上面三个步骤，每个步骤都是根据当前序列的状态，将问题转化为已知解的子问题 (最初的已知解的子问题是当m==0或n==0时)，从而求出当前问题的解。

由此便得出了该问题的状态转移方程，数学描述如下：

现有两个序列X={x ₁ ,x ₂ ,x _3， ...x _i }，Y={y ₁ ,y ₂ ,y _3， ....，y _i }，

设一个C[i,j]: 保存X _i 与Y _j 的LCS的长度

动态规划之最长公共子序列(LCS)

最后，该算法的python实现：

1 # 最长公共子序列问题  2 __author__ = 'ice'  3   4   5 # arr_x,arr_y [0 ~ length-1]  6 # subarr_len [0,1~x_length][0,1~y_length]  7 # flag [0 ~ x_length-1][0 ~ y_length]  8   9  10 def lcs_length(arr_x, arr_y): 11     x_length = len(arr_x) 12     y_length = len(arr_y) 13     subarr_len = [[0 for j in range(y_length + 1)] for i in range(x_length + 1)] 14     flag = [[0 for j in range(y_length)] for i in range(x_length)] 15     for i in range(1, x_length + 1): 16         for j in range(1, y_length + 1): 17             if arr_x[i - 1] == arr_y[j - 1]: 18                 subarr_len[i][j] = subarr_len[i - 1][j - 1] + 1 19                 flag[i - 1][j - 1] = 1 20             elif subarr_len[i - 1][j] >= subarr_len[i][j - 1]: 21                 subarr_len[i][j] = subarr_len[i - 1][j] 22                 flag[i - 1][j - 1] = 2 23             else: 24                 subarr_len[i][j] = subarr_len[i][j - 1] 25                 flag[i - 1][j - 1] = 3 26     return {'subarr_length': subarr_len[x_length][y_length], 'flag': flag} 27  28  29 def lcs(arr_x, x_i, y_j, flag, result): 30     if x_i < 0 or y_j < 0: 31         return 32     if flag[x_i][y_j] == 1: 33         lcs(arr_x, x_i - 1, y_j - 1, flag, result) 34         result.append(arr_x[x_i]) 35     elif flag[x_i][y_j] == 2: 36         lcs(arr_x, x_i - 1, y_j, flag, result) 37     elif flag[x_i][y_j] == 3: 38         lcs(arr_x, x_i, y_j - 1, flag, result) 39  40  41 array_x = ['a', 'b', 'c', 'b', 'd', 'a', 'b'] 42 array_y = ['b', 'd', 'c', 'a', 'b', 'a'] 43 longest_common_subsequence = [] 44 lcs_info = lcs_length(array_x, array_y) 45 lcs(array_x, len(array_x) - 1, len(array_y) - 1, lcs_info['flag'], longest_common_subsequence) 46 print(longest_common_subsequence)

正文到此结束