X = ABCBDAB

Y = BDCABA

가장 긴 길이의 공통 부 문자열을 찾는 문제

DP 문제

Xn = x1x2x3..xn. X3 = x1x2x3

Ym = y1y2y3..ym. Y2 = y1y2

LCS(Xn, Ym) ⇒ Xn 과 Ym 의 가장 긴 공통 부 문자열의 길이

위 식을 작은 문제로 쪼개야 한다.

LCS(Xi, Yj) ⇒ Xi 과 Yj 의 가장 긴 공통 부 문자열의 길이

xi 와 yj 가 같은 경우와 다른경우

같은 경우 : LCS(Xi, Yj) = LCS(Xi-1,Yj-1) + 1

다른 경우: LCS(Xi,Yj)= max(LCS(Xi,Yj-1), LCS(Xi-1, Yj))

만약에 최장 공통 부분 수열의 길이가 아니라 수열 자체를 구하고 싶다면 맨 아래에서 부터

역행 하면 된다 LCS(7,6)에서 시작해서 위 와 왼쪽 둘중에 하나로 이동하면 된다.

7,6 에서 위와 왼쪽이 똑같으니 아무 쪽으로 가도 된다. 이때 위로 가보자 6,6 이때 x6 == y6 이니까

최장 공통 부분 수열의 마지막에 A가 들어간다.그리고 하나를 넣었으니 왼쪽 위 대각 으로 이동한다 5,5

x5 ≠ y5 이니까 왼쪽과 위 중에 큰 값으로 이동 4,5 이때 x4 == y5 니까 또 B 넣고 왼쪽 위 대각 이동

이런 식으로 채운다.