[알고리즘/백준] 9251번 : LCS(python)

처음에 어떻게 푸는지 몰라서 답을 봤다. 문자를 하나씩 추가하면서 푸는 문제이다.

a1 = input()
a2 = input()
len1 = len(a1)
len2 = len(a2)
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        if a1[i - 1] == a2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[len1][len2])