n, m = map(int, input().split()) s1 = input().strip() s2 = input().strip() dp = [[0]*(m+1) for _ in range(n+1)] # # n row m col for i in range(n): for j in range(m): if s1[i] == s2[j]: dp[i+1][j+1] = dp[i][j] + 1 else: dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]) print(dp[-1][-1])
dp[i][j] 表示子序列 s1i 和 s2j的最长公共子序列的长度
当s1i = s2j 的时候, 找出 s1i-1 和 s2j-1 的最长公共子序列然后加上s1i即可得到s1i 和 s2j的最长公共子序列. 注:子序列不要求连续,字串才要求连续
当s1i != s2j 的时候, 求s1i-1 和 s2j 与 s1i 和 s2j-1 的最长公共子序列,取最大值即可 [没得选就往直前的状态里找一个最大的,dp的特性就是最近的最大一定是已经求出来的所有结果中的最大]
因此可得出状态转移方程:
当s1i = s2j 的时候:
dp[i+1][j+1] = dp[i][j] + 1当s1i != s2j 的时候:
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])最后,二维数组的最后一个元素就是答案