蓝桥杯—蓝肽子序列—动态规划

蓝肽子序列

dp[i] [j]表示L1,L2 前 i ,j 个字段有多少个公共子序列，对于一个Xi 和 Yj（L1,L2的前i, j 个字段形成序列.

如果xi=yj (第i,j字段)，则dp[i] [j]=dp[i-1] [j-1]+1(前面的公共字段加一).

否则，dp[i] [j]=max(dp[i-1] [j] , dp[i] [j-1]) ,考虑前后情况的最大值。

最后输出dp[n] [m]。

'''
本题的思路就是先将蓝肽质完全分割为一个个蓝肽子序列，
然后再用动态规划算法求最大公共子序列
'''
s1 = input()
s2 = input()
list_s1 = []  # 用于储存分割好的蓝肽子序列
list_s2 = []
a = ''  # 用于分割单词 ---> 蓝肽子序列
b = ''  # 作用同上
for i in s1:
    if 'A' <= i <= 'Z':  # 判断i是否是大写字母大小写字母ASCII值不在同一个区间
        if a != '':  # 说明又碰到了另一个大写字母，即其它蓝肽的头部
            list_s1.append(a)
            a = ''  # 开始搜集下一个蓝肽子序列
    a += i  # 重建a
list_s1.append(a)  # 将最后一个蓝肽子序列加入
# 以下为搜集s2中蓝肽子序列的过程，与上面的步骤大致相同
for i in s2:
    if 'A' <= i <= 'Z':
        if b != '':
            list_s2.append(b)
            b = ''
    b += i
list_s2.append(b)
n = len(list_s1)
m = len(list_s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
# 经典动态规划
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if list_s1[i - 1] == list_s2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[n][m])