<filename>ch04_dynamic/at404_lcs.py<gh_stars>1-10
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# 最长公共子序列：longest-common-subsequence
# author: XiongNeng
"""
Topic: 一个子序列代表，将一个序列中去掉若干元素后得到的序列，可以间隔。
    公共子序列就是，序列A和序列B的公共子序列
    最长公共子序列就是，公共子序列里面长度最长的。

    思路：
    接受两个序列<x1,x2,...xm>和<y1,y2,...yn>作为输入
    将两个序列安装下标变成矩阵或者是二维数组c(m+1 * n+1)
    按行主次序(row-major-order)计算表项，即首先计算C的第一行，然后是第二行。。
    另外还维护一个二维数组b(m * n)，b[i,j]指向的表项对应计算c[i,j]时选择的子问题最优解
    c[m-1][n-1]保存了X和Y的LCS的长度
Desc : 
"""

def lcs(arr1, arr2):
    m = len(arr1)
    n = len(arr2)
    c = [[0 for kk in range(n + 1)] for kk in range(m + 1)]
    b = [[-1 for kk in range(n)] for kk in range(m)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if arr1[i - 1] == arr2[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i - 1][j - 1] = '↖'  # 代表此元素放入LCS
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
                b[i - 1][j - 1] = '↑'  # 行减1，往上
            else:
                c[i][j] = c[i][j - 1]
                b[i - 1][j - 1] = '←'  # 列减1，往左
    rlcs = []
    get_lcs_arr(b, arr1, len(arr1) - 1, len(arr2) - 1, rlcs)
    print('LCS长度为:%d' % c[m][n])
    print('一个最优解:%s' % str(rlcs))
    return c[m][n], rlcs

def get_lcs_arr(b, X, i, j, arr):
    if i < 0 or j < 0:
        return
    if b[i][j] == '↖':
        get_lcs_arr(b, X, i - 1, j - 1, arr)
        arr.append(X[i])
    elif b[i][j] == '↑':
        get_lcs_arr(b, X, i - 1, j, arr)
    else:
        get_lcs_arr(b, X, i, j - 1, arr)

if __name__ == '__main__':
    x = ['A', 'B', 'D', 'A', 'C', 'K']
    y = ['B', 'D', 'D', 'E', 'C', 'K', 'M']
    lcs(x, y)