最长子序列（动态规划）

2023-07-19

完成时间：大二上

问题描述

最长公共子序列问题：若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。如果给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。现给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，要求使用动态规划算法思想，找出X和Y的最长公共子序列。

问题建模

先建立一个二维列表，构成一个矩阵flag[][]，将序列x的下标作为矩阵的横坐标，序列y作为纵坐标，默认全部值为0，将x[0]分别与yi进行比较，若相同则将将flag[0][i]+1，然后对x[1]重复上述上述步骤，直到遍历完整个矩阵，然后统计一条斜线上1的个数，其中1最多的斜线对应的坐标即为所求解。

源码

a = []
b = []
while(1):
    n = input("请给序列x赋值(输入空格退出)：")
    if n == " ":
        break
    else:
        a.append(n)
while(1):
    n = input("请给序列y赋值(输入空格退出)：")
    if n == " ":
        break
    else:
        b.append(n)
l1 = []
def lcs(a,b):
    lena=len(a)
    lenb=len(b)
    c=[[0 for i in range(lenb+1)] for j in range(lena+1)]
    flag=[[0 for i in range(lenb+1)] for j in range(lena+1)]
    for i in range(lena):
        for j in range(lenb):
            if a[i]==b[j]:
                c[i+1][j+1]=c[i][j]+1
                flag[i+1][j+1]='ok'
            elif c[i+1][j]>c[i][j+1]:
                c[i+1][j+1]=c[i+1][j]
                flag[i+1][j+1]='left'
            else:
                c[i+1][j+1]=c[i][j+1]
                flag[i+1][j+1]='up'
    return c,flag
def Lcs(flag,a,i,j):
    if i == 0 or j == 0:
        return
    if flag[i][j] == 'ok':
        Lcs(flag,a,i-1,j-1)
#       print(a[i-1],end='')
        l1.append(a[i-1])
    elif flag[i][j]=='left':
        Lcs(flag,a,i,j-1)
    else:
        Lcs(flag,a,i-1,j)
c,flag=lcs(a,b)
Lcs(flag,a,len(a),len(b))
print(l1)

运行结果

时间复杂度分析

动态规划的时间复杂度分为两部分：状态计算的时间复杂度，每个状态的状态转移时间复杂度。
所有状态计算的时间复杂度为 O ( a ) O(a) O(a)，单个状态的状态转移时间复杂度为 O ( b ) O(b) O(b)，则整个动态规划的求解过程的时间复杂度就是 O ( a b ) O(ab) O(ab)。
线性DP 的状态数就是 O ( n ) O(n) O(n)，状态转移的时间复杂度一般为 O ( 1 ) O(1) O(1) 或者 O ( n ) O(n) O(n)，也有 O ( l o g 2 n ) O(log_2n) O(log2n) 的，可能利用二分枚举进行状态转移，比如最长单调子序列

说明

本实验完成于大二上学期（2021下半年），所使用语言为Python