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

n,m = map(int,input().split())
s1 = input()
s2 = input()
# 空间优化方案(滚动数组)
curr = [0]*(m+1)
for i in range(1,n+1):
    prev = curr
    curr = [0]*(m+1)
    for j in range(1,m+1):
        if s1[i-1] == s2[j-1]:
            curr[j] = prev[j-1]+1
        else:
            curr[j] = max(prev[j],curr[j-1])
print(curr[m])