[고급 알고리즘] Dynamic Programming: Longest Common Subsequence

1. Longest Common Subsequence (LCS. 최장 공통 수열)

• 주어진 수열들의 부분 수열이 되는 수열들, 중 가장 긴 것을 찾는 문제입니다.

 

점화식

${\displaystyle LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)+1&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cases}}}$

 

예시: XMJYAUZ, MZJAWXU

 

2. 풀이

dp = new int[a.length+1][b.length+1];

for (int i = 0; i <= a.length; i++) {
    for (int j = 0; j <= b.length; j++) {
        if (i == 0 || j == 0) dp[i][j] = 0;
        else if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
        else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
}

 

 

 

출처

• Wiki - Longest common subsequence