Python3_最长公共子序列
作者:
心牢
,
2024-02-06 19:09:24
,
所有人可见
,
阅读 43
"""
动态规划:
状态表示:
f[i][j]:所有在第一个序列中前i个字母中出现,且在第二个序列前j个字母出现的子序列
属性:最大值
状态计算:
集合如何划分才能包含所有情况
00:不选第i个字母,且不选第j个字母
01:不选第i个字母,且选第j个字母
10:选第i个字母,且不选第j个字母
11:选第i个字母,且选第j个字母:这个需要a[i]==b[j]
00这个情况是被01和10同时包含的,因为是求最大值
且01,10不一定包含a[i]或者b[j],但是01,10可以用f[i - 1][j]和f[i][j - 1]表示
从上面状态表示的含义来看,01,10以及00时被包含了
故状态转移方程:
f[i][j] = max(f[i - 1][j - 1] + 1, f[i - 1][j], f[i][j - 1])
"""
n, m = map(int, input().strip().split())
a = list(input())
b = list(input())
a.insert(0, ' ')
b.insert(0, ' ')
f = [[0] * 1100 for _ in range(1100)]
for i in range(1, n + 1):
for j in range(1, m + 1):
f[i][j] = max(f[i - 1][j], f[i][j - 1])
if a[i] == b[j]:
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)
print(f[n][m])