DP LCS(Logest Common Subsequence) & 백준 9251번 python

LCS란?

 - Longest Common Subsequence 최장 공통 부분 수열, 최장 문자열을 찾는 것이다

 - X[ ~ ], Y[ ~ ], Z[ ~ ] 일때

 - Xm = Yn이면 Zk = Xm = Yn이고 Z(k-1)은 X(m-1)과 Y(n-1)의 LCS이다 첫번째 정의로 인해                                                                 = (1+matrix(i-1][j-1]) = 1 + max(LCS(X(m-1)),LCS(Y(n-1)))

 - Xm /= Yn이면, Zk /= Xm은 Z가 X(m-1)과 Y의 LCS임을 의미한다.

 - Xm /= Yn이면, Zk /= Yn은 Z가 Y(n-1)과 X의 LCS임을 의미한다. 두 정의로 인해 = max(matrix[i][j-1],matrix[i-1][j])

 

출처 : https://kashyapv.com/dp/2020/05/15/lcs.html

 

 

 

 

https://www.acmicpc.net/problem/9251

9251번: LCS

 

import sys
sys.stdin = open('inputs.text')

a = sys.stdin.readline().rstrip()
b = sys.stdin.readline().rstrip()
matrix = [[0]*(len(b)+1) for _ in range(len(a)+1)]

for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
        if a[i-1] == b[j-1]:
            matrix[i][j] = matrix[i-1][j-1] + 1
        else:
            matrix[i][j] = max(matrix[i][j-1],matrix[i-1][j])

print(matrix[-1][-1])