题目描述

f[i][j]
状态表示：a以第i位结尾，b以第j位结尾，的最长字串长度
状态转移：
如果a第i位和b的第j位相同。那么f[i][j] = max(f[i-1][j-1],f[i][j])
如果不相同： 那么说明f[i][j]的最大值一定在f[i-1][j]和f[i][j-1]中取得。

Python 代码

N = 1010
M = 1010
f = [[0 for _ in range(N)] for _ in range(M)] 

if __name__ == '__main__':
    n,m = map(int,input().split())
    a = list(map(str,input()))
    b = list(map(str,input()))
    for i in range(n):
        for j in range(m):
            if a[i] == b[j]:
                f[i][j] = max(f[i][j],f[i-1][j-1]+1)
            else:
                f[i][j] = max(f[i-1][j],f[i][j-1])
    print(f[n-1][m-1])