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

import sys

# for line in sys.stdin:
#     a = line.split()
#     print(int(a[0]) + int(a[1]))

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

# 方法一：普通写法，空间复杂度为 O(mn)
# dp = [[0]*m for _ in range(n)]

# for i in range(n):
#     if s1[i] == s2[0]:
#         dp[i][0] = 1
# for j in range(m):
#     if s1[0] == s2[j]:
#         dp[0][j] = 1

# for i in range(1, n):
#     for j in range(1, m):
#         if s1[i] == s2[j]:
#             dp[i][j] = 1 + dp[i-1][j-1]
#         else:
#             dp[i][j] = max(dp[i-1][j], dp[i][j-1])

# print(dp[-1][-1])

# 方法二：使用滚动数组降低空间复杂度
# 关键是在于每一次 i 取不同值的时候，dp[j] 覆盖掉 i-1 时 dp[j] 的情况
dp = [0]* m
for i in range(n):
    prev = dp[0]
    for j in range(m):
        temp = dp[j] # 记录下当前值，因为计算dp[j+1]的时候要用到
        if s1[i] == s2[j]:
            if j > 0:
                dp[j] = prev + 1  # 方法一中的 dp[i][j] = 1 + dp[i-1][j-1]
				# 因为计算 dp[j] 的时候 i-1 时的 dp[j-1]已经被覆盖掉了，所以必须用 prev 提前记录
            else:
                dp[j] = 1
        else:
            if j > 0:
                dp[j] = max(dp[j], dp[j-1]) # 方法一中的 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        prev = temp
print(dp[-1])