[BOJ][DP] 9251. LCS

문제 -> https://www.acmicpc.net/problem/9251

이 문제도 아주 곤욕을 치뤘다.

http://twinw.tistory.com/126 <- 이분의 친절한 풀이 덕에 

해답을 찾았다. 

1. 2차원 배열로 dp 표를 만든다.

2. 각 문자열의 길이대로 반복을 하여 비교 한다.

3. 비교 할 시, 두 가지 경우로 나뉘는데

1) 알파벳이 같은 경우 

-> dp[i][j] = dp[i-1][j-1] + 1;

2) 알파벳이 다른 경우

-> dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

왜 위와 같이 나오는지는

위의 링크를 가서 설명을 보면 명쾌히 풀릴 것이다.

감사드립니다 White Whale님..

소스(Github)