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

n,m = map(int,input().split())
s1 = input()
s2 = input()
# **dp[i][j]定义为s1前i个字符和s2前j个字符的最长公共子序列
# 在已知dp[x][y](x<i,y<i)的前提下如何得到dp[i][j]？
# if s1[i-1] == s2[j-1]:dp[i][j] = dp[i-1][j-1]+1
# **else:dp[i][j] = max(dp[i][j-1],dp[i-1][j])(呃，似懂非懂的)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1] == 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])