내 풀이
import sys, copy
from collections import deque
str1 = list(input())
str2 = list(input())
dp = [[0]* (len(str2)+1) for _ in range(len(str1)+1)]
for i in range(1, len(str1)+1):
for j in range(1, len(str2)+1):
if str1[i-1] == str2[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(max(max(dp)))예전에 풀었던 문제인데 풀지 못했다.
점화식 설명
dp[i][j]는 str1의 i번째까지와 str2의 j번째까지 비교했을 때 가장 긴 수열이다.Case1: 만약 str1의 i번째 문자와 str2의 j번째 문자가 다르다면 길이는 dp[i-1][j]와 dp[i][j-1]중 최대 값이다 (기존에 주어진 문자열로 만들 수 있던 최대 길이)
Case2: 만약 str1의 i번째 문자와 str2의 j번째 문자가 같다면 dp[i-1][j-1] + 1이다. (두 글자가 추가되기 전 가장 큰 길이 + 1)
