최장 공통 부분 수열 편집하기 (부분)

==점화식==
'''기본 아이디어'''

* 기저 사례(Base Case)
** 하나의 문자열이 비어 있으면 공통 부분 수열이 없으므로 LCS 길이는 0.
* 두 문자열의 마지막 문자가 같다면
** LCS(X[:-1], Y[:-1]) + 1 (즉, 두 문자열에서 각각 마지막 문자를 제거하고 나머지 문자열의 LCS를 구한 후 1을 더함).
* 두 문자열의 마지막 문자가 다르면
** 마지막 문자를 제거한 두 가지 경우 중 더 긴 LCS를 선택.
** LCS(X[:-1], Y) (X의 마지막 문자 제외)
** LCS(X, Y[:-1]) (Y의 마지막 문자 제외)
*** 이 둘 중 더 긴 값을 선택하면 최적의 해를 보장할 수 있음.

동적 계획법을 이용하여 최장 공통 부분 수열을 계산하는 점화식은 다음과 같다.
*X[i] == Y[j]이면
**LCS(i, j) = LCS(i-1, j-1) + 1
*X[i] ≠ Y[j]이면
**LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))