AcWing 897. 一图全解最长公共子序列问题~（算法基础课）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 897. 一图全解最长公共子序列问题~（算法基础课）原题链接简单

作者：

Mr-Black , 2023-03-25 19:12:53 , 所有人可见 , 阅读 919

21

12

原理

闫氏DP分析法yyds!
一图胜千言~
公共最长子序列.png

代码

原理很复杂，代码却很简洁，就是这种高级感啊....

n,m = map(int,input().split())
a = " "+input()
b = " "+input()
f = [[0 for i in range(len(b)+1)] for j in range(len(a)+1)]
for i in range(1,len(a)):
    for j in range(1,len(b)):
        f[i][j] = max(f[i-1][j], f[i][j-1])
        if a[i] == b[j]: f[i][j] = max(f[i][j],f[i-1][j-1]+1)
print(f[n][m])