[BOJ] 9251

다이나믹프로그래밍

• https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182
• 큰 문제를 부분 문제로 나눠 해결한다
• 부분문제가 반복된다
• 즉, 분할정복으로 문제를 풀면서, 반복되는 답을 저장해두는 기법이 동적프로그래밍이다(다이나믹프로그래밍)

LCS의 경우

• 길이 n, m 의 LCS는 길이 (n-1, m), (n, m-1), (n-1, m-1) 의 LCS 와 상관관계가 있다.
  - 큰 문제를 부분 문제로 나눠 해결한다
• 각 문자열의 마지막 문자가 같으면 LCS(n-1, m-1) + 1
• 각 문자열의 마지막 문자가 다르면 max(LCS(n-1, m), LCS(n, m-1))

"""
DP
"""

import sys

# sys.stdin = open('9251.txt')

seq1 = input()
seq2 = input()

n1 = len(seq1)
n2 = len(seq2)
data = [[0 for _ in range(n1+1)] for _ in range(n2+1)]

for i in range(n1):
    for j in range(n2):
        if seq1[i] == seq2[j]:
            data[j + 1][i + 1] = data[j][i] + 1
        else:
            data[j + 1][i + 1] = max(data[j + 1][i], data[j][i + 1])

print(data[n2][n1])