[DP 알고리즘] LCS

기출: 백준 #9251

 

stringA = ' ' + input()
stringB = ' ' + input()
m = len(stringA)
n = len(stringB)


LCS = [[0 for __ in range(n)] for _ in range(m)]

for i in range(1, m):
    for j in range(1, n):
        if stringA[i] == stringB[j]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
    
print(LCS[m-1][n-1])