最长公共子序列（动态规划）

**【问题描述】**使用动态规划算法解最长公共子序列问题，具体来说就是，依据其递归式，自底向上的方式依次计算得到每个子问题的最优值。

**【输入形式】**在屏幕上输入两个序列X和Y，序列各元素数间都以一个空格分隔。

**【输出形式】**矩阵c，其中c(i,j)中存放的是：序列Xi = {x1, …, xi}和序列Yj = {y1, …, yj}的最长公共子序列的长度。序列X和Y的最长公共子序列。

【样例输入】

A B C B D A B

B D C A B A

【样例输出】

[[0 0 0 0 0 0 0]

[0 0 0 0 1 1 1]

[0 1 1 1 1 2 2]

[0 1 1 2 2 2 2]

[0 1 1 2 2 3 3]

[0 1 2 2 2 3 3]

[0 1 2 2 3 3 4]

[0 1 2 2 3 4 4]]

BCBA

【样例说明】

输入：第一行输入序列X的各元素，第二行输入序列Y的各元素，元素间以空格分隔。

输出：矩阵c，和序列X和Y的最长公共子序列。

【评分标准】根据输入得到准确的输出。

python实现：

import numpy as np


def lcs_length(x, y, m, n, b, c):
    for i in range(1, m+1):
        c[i, 0] = 0
    for j in range(1, n+1):
        c[0, j] = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i] == y[j]:
                c[i, j] = c[i-1, j-1]+1
                b[i, j] = 1
            elif 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


def print_lcs(b, x, i, j):
    if i == 0 or j == 0:
        return
    if b[i, j] == 1:
        print_lcs(b, x, i-1, j-1)
        print(x[i], end="")
    elif b[i, j] == 2:
        print_lcs(b, x, i-1, j)
    else:
        print_lcs(b, x, i, j-1)


def main():
    x = list(input().split())
    y = list(input().split())
    m = len(x)
    n = len(y)
    x.insert(0, 0)
    y.insert(0, 0)
    b = np.zeros((m + 1, n + 1), dtype=np.int8)
    c = np.zeros((m + 1, n + 1), dtype=np.int8)
    lcs_length(x, y, m, n, b, c)
    print(c)
    print_lcs(b, x, m, n)


if __name__ == '__main__':
    main()