动态规划之最长公共子序列问题(未竟)

算法描述

递归式

\[ c[i, j] = \left\{ \begin{matrix} \begin{align} & {0} && {if \quad i = 0 \; or \; j = 0,} \\ & {c[i - 1, j - 1] + 1} && {if \quad i, j > 0 \; and \; x_i = y_j,} \\ & {max(c[i, j - 1], c[i - 1, j])} && {if \quad i, j > 0 \; and \; x_i \neq y_j.} \\ \end{align} \end{matrix} \right. \]

伪码

一个示例

算法的 Python 实现

# 最长共同子序列动态规划算法
def lcs_length(X:str, Y:str):
    m = len(X)
    n = len(Y)
    b = [[0 for j in range(n + 1)] for i in range(m + 1)] # b 只使用 1..m
    c = [[0 for j in range(n + 1)] for i in range(m + 1)] # c 只使用 1..m
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = [i - 1, j - 1] # 存入路径
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
                b[i][j] = [i - 1, j]
            else:
                c[i][j] = c[i][j - 1]
                b[i][j] = [i, j - 1]
    return [c, b]

def print_lcs(b:list, X:str, i:int, j:int):
    if i == 0 or j == 0:
        return
    if b[i][j] == [i - 1, j - 1]:
        print_lcs(b, X, i - 1, j - 1)
        print(X[i - 1], end=' ')
    elif b[i][j] == [i - 1, j]:
        print_lcs(b, X, i - 1, j)
    else:
        print_lcs(b, X, i, j - 1)

if __name__ == '__main__':
    # S2 = 'BDCABA'
    # S1 = 'ABCBDAB'
    S1 = 'ACCGGTCGAGATGCAG'
    # S2 = 'ACCGGTCGAGATGCAG'
    S2 = 'GTCGTTCGGAATGCAT'
    res = lcs_length(S1, S2)
    print(res)
    print('----------')
    for each in res[0]:
        print(each)
    print('----------')
    print_lcs(res[1], S1, len(S1), len(S2))
    print('\n----------')
    print(res[0][len(S1)][len(S2)])

运行结果

[[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], [0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3], [0, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4], [0, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5], [0, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6], [0, 1, 2, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6], [0, 1, 2, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 7, 7], [0, 1, 2, 3, 4, 4, 4, 4, 5, 6, 6, 6, 6, 7, 7, 7, 7], [0, 1, 2, 3, 4, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7, 8, 8], [0, 1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 7, 8, 8, 8, 8, 9], [0, 1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 7, 8, 9, 9, 9, 9], [0, 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 8, 9, 10, 10, 10], [0, 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 8, 9, 10, 11, 11], [0, 1, 2, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9, 10, 11, 11]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8], [0, 9], [0, 9], [0, 10], [1, 11], [1, 12], [1, 13], [0, 14], [1, 15]], [0, [1, 1], [1, 2], [1, 2], [2, 3], [2, 4], [2, 5], [1, 6], [2, 7], [2, 8], [1, 10], [1, 11], [1, 12], [1, 13], [1, 13], [2, 14], [2, 15]], [0, [2, 1], [2, 2], [2, 2], [2, 4], [2, 5], [2, 6], [2, 6], [3, 7], [3, 8], [3, 9], [3, 10], [3, 11], [3, 12], [2, 13], [2, 15], [2, 16]], [0, [3, 0], [4, 1], [3, 3], [3, 3], [4, 4], [4, 5], [3, 7], [3, 7], [3, 8], [4, 9], [4, 10], [4, 11], [3, 12], [4, 13], [4, 14], [4, 15]], [0, [4, 0], [4, 2], [4, 3], [4, 3], [4, 5], [4, 6], [4, 7], [4, 7], [4, 8], [5, 9], [5, 10], [5, 11], [4, 12], [5, 13], [5, 14], [5, 15]], [0, [5, 1], [5, 1], [6, 2], [5, 4], [5, 4], [5, 5], [6, 6], [5, 8], [5, 9], [5, 10], [5, 11], [5, 11], [6, 12], [6, 13], [6, 14], [5, 15]], [0, [6, 1], [6, 2], [6, 2], [7, 3], [6, 5], [6, 6], [6, 6], [7, 7], [6, 9], [6, 10], [6, 11], [6, 12], [6, 13], [6, 13], [7, 14], [7, 15]], [0, [7, 0], [7, 2], [7, 3], [7, 3], [8, 4], [8, 5], [7, 7], [7, 7], [7, 8], [8, 9], [8, 10], [7, 12], [7, 12], [7, 14], [7, 15], [7, 16]], [0, [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8], [8, 9], [8, 9], [8, 10], [9, 11], [8, 13], [8, 14], [8, 14], [9, 15]], [0, [9, 0], [9, 2], [9, 3], [9, 3], [9, 5], [9, 6], [9, 7], [9, 7], [9, 8], [9, 10], [9, 11], [9, 12], [9, 12], [10, 13], [9, 15], [9, 16]], [0, [10, 1], [10, 2], [10, 3], [10, 4], [10, 5], [10, 6], [10, 7], [10, 8], [10, 9], [10, 9], [10, 10], [11, 11], [10, 13], [10, 14], [10, 14], [11, 15]], [0, [11, 1], [11, 1], [11, 3], [11, 4], [11, 4], [11, 5], [12, 6], [11, 8], [11, 9], [11, 10], [11, 11], [11, 11], [12, 12], [12, 13], [11, 15], [11, 15]], [0, [12, 0], [12, 2], [12, 3], [12, 3], [12, 5], [12, 6], [12, 7], [12, 7], [12, 8], [12, 10], [12, 11], [12, 12], [12, 12], [13, 13], [13, 14], [12, 16]], [0, [13, 1], [13, 2], [13, 2], [13, 4], [13, 5], [13, 6], [13, 6], [13, 8], [13, 9], [13, 10], [13, 11], [13, 12], [13, 13], [13, 13], [14, 14], [14, 15]], [0, [14, 1], [14, 2], [14, 3], [14, 4], [14, 5], [14, 6], [14, 7], [14, 8], [14, 9], [14, 9], [14, 10], [14, 12], [14, 13], [14, 14], [14, 14], [15, 15]], [0, [15, 0], [15, 2], [15, 3], [15, 3], [15, 5], [15, 6], [15, 7], [15, 7], [15, 8], [15, 10], [15, 11], [15, 12], [15, 12], [15, 14], [15, 15], [15, 16]]]]
----------
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]
[0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3]
[0, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4]
[0, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5]
[0, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6]
[0, 1, 2, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6]
[0, 1, 2, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 7, 7]
[0, 1, 2, 3, 4, 4, 4, 4, 5, 6, 6, 6, 6, 7, 7, 7, 7]
[0, 1, 2, 3, 4, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7, 8, 8]
[0, 1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 7, 8, 8, 8, 8, 9]
[0, 1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 7, 8, 9, 9, 9, 9]
[0, 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 8, 9, 10, 10, 10]
[0, 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 8, 9, 10, 11, 11]
[0, 1, 2, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9, 10, 11, 11]
----------
C G T C G A A T G C A 
----------
11