题解 | 最长公共子序列(一)

m, n = map(int, input().split())
s1 = input().strip()
s2 = input().strip()

if m < n:
    s1, s2 = s2, s1
    m, n = n, m
dp = [[0] * (n+1) for _ in range(2)]

for i in range(1, m+1):
    for j in range(1, n+1):
        # 假设不加入最后一个字符
        max_i = max(dp[(i-1)%2][j], dp[i%2][j-1])
        if s1[i-1] == s2[j-1]:  # 两者最后一个字符相等的时候才能够判断是否能够更大
            max_i = max(max_i, dp[(i-1)%2][j-1]+1)
        dp[i%2][j] = max_i
print(dp[m%2][n])