python实现最长公共子序列动态规划问题

时间:2022-06-23 18:42:36

用python写了一个用动态规划方法求两个序列的最长公共子序列,代码哪里有问题请指点。

 
 
# -*- coding: utf-8 -*-
# author:Huangyuliang
# 最长公共子序列问题
# 求 a,b 序列的最长公共子序列
import numpy as np

def lcs_len(a,b):
    n = len(a)
    m = len(b)
    p = n+1
    q = m+1
    c = np.zeros((p,q))
    val = c.copy()
    for i in range(1,p):
        for j in range(1,q):
            if a[i-1] == b[j-1]:
                c[i,j] = c[i-1,j-1] + 1
                val[i,j] = 0   # 在左上角
            elif c[i-1,j] >= c[i,j-1]:
                c[i,j] = c[i-1,j]
                val[i,j] = 1   # 在上方
            else:
                c[i,j] = c[i,j-1]
                val[i,j] = 2   # 在左方
    k = int(c[n,m])  # k 等于 最长公共子序列的元素个数
    print "k =",k
    G = range(k+1)   # G 用来保存最长公共子序列
    while k>0:
        if val[n,m]==1:
            n-=1
        elif val[n,m]==2:
            m-=1
        else:
            G[k] = a[n-1]
            k-=1
            n-=1
            m-=1
    return G[1:]

a,b = [1,2,3,5,7,8,9],[1,2,3,4,5,9]
h = lcs_len(a,b)
print h
输出结果:
k = 5
h = [1,2,3,5,9]