from acwing 897 时间限制：1s 空间限制：64MB
题目描述：
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式：第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式：输出一个整数，表示最大长度。
数据范围：1≤N,M≤1000
输入样例：4 5 acbd abedc输出样例：
3
动态规划模板题。
如果两个序列（a1，a2，，，an和b1，b2，，，bn）的最后一位相等，那么他们的最长公共子序列问题将转化为a1，a2，an-1和b1，b2，，，bn-1这两个序列的最长公共子序列的结果加上1；如果不相等，他们的最长公共子序列问题将转化为（a1，a2，，，an-1和b1，b2，，，bn）或者（a1，a2，，，an和b1，b2，，，bn-1）这两情况的最大值。
n,m = map(int,input().split())
s1 = ' ' + input()
s2 = ' ' + input()
ans = [[0] * (m + 1) for i in range(0,n + 1)]
for i in range(1,n + 1):
for j in range(1,m + 1):
if s1[i] == s2[j]:
ans[i][j] = ans[i - 1][j - 1] + 1
else:
ans[i][j] = max(ans[i - 1][j],ans[i][j - 1])
print(ans[n][m])
