백준 9252번 링크 LCS Longest common subsequence를 찾는 전형적인 DP 문제다. 점화식은 다음과 같다. $$ DPi = \begin{cases} DPi - 1 + 1 &\text{if } str[i] == str[j] \\ max(DPi - 1, DPi) &\text{o.w. }\end{cases} $$ 해당 문제에서는 결과값으로 LCS의 길이 뿐만 아니라 문자열도 요구한다. 두가지 방법이 있다. 2차원 배열을 만들어 해당 칸으로 온 방향을 기록해둔다. 단순하게 역추적한다. 2번 방법을 적용하여 풀었다. 코드