[DP] 9251번 - LCS (8일차)

#첫번째 문자열 입력
l1 = input()
#두번째 문자열 입력
l2 = input()

#첫번째 문자열의 길이
n = len(l1)
#두번째 문자열의 길이
m = len(l2)

#dp = 해당 지점까지의 가장 긴 공통 부분 수열의 길이를 저장
#단, i,j가 각각 0일때 dp의 값을 0으로 미리 채움 (인덱스 에러 방지용)
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

#i(l1의 각 문자)를 중심으로
for i in range(1,n+1):

    #j(l2 각 문자)에 대해 탐색
    for j in range(1,m+1):

        #ㅣ1의 문자와 l2의 문자가 같을 때
        if(l1[i-1] == l2[j-1]):
            #dp[i-1][j] = l1의 직전 문자, l2의 해당 인덱스까지 최고 수열
            #dp[i][j-1] = l1의 해당 문자, l2의 인덱스 직전까지 최고 수열
            #dp[i-1][j-1]+1 = l1의 직전 문자, l2의 인덱스 직전까지 최고 수열에 길이를 더함
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1)

        else:
            #dp[i-1][j-1] = l1의 직전 문자, l2의 직전 인덱스까지 최고 수열
            #dp[i][j-1] = l1의 해당 문자, l2의 직전 인덱스까지 최고 수열
            #dp[i-1][j] = l1의 직전 문자, l2의 해당 인덱스까지 최고 수열
            dp[i][j] = max(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])

#l1과 l2를 끝까지 탐색한 상황에서 가장 긴 수열 길이 출력
print(dp[-1][-1])