최장 공통 부분열(DP)

문자열 S1, S2, ... , Sn과  T1, T2, ... , Tn이 주어져 있습니다. 이 둘의 공통 부분 문자열의 길이의 최대 값을 구하세요. 단 문자열 S1S2...Sn의 부분 문자열이란 Si1, Si2, ... Sim(i1 < i2 < ... < im)로 표현 가능한 문자열을 말합니다.

제약

1 <= n, m <= 1000

 

dp[i][j] = S1 ~ Si와 T1 ~ Tj의 최장 공통 부분 문자열의 길이

dp[0][j] = dp[i][0] = 0;

dp[i][j] = dp[i - 1][j - 1] + 1 (S[i] == T[i])

            max(dp[i - 1][j], dp[i][j - 1]) (그외)

 

int n;

int s[1000], t[1000];

int dp[1001][1001];

 

inf main(){

  //입력 ...

 

  for(int i = 0; i < n + 1; ++i)

    dp[i][0] = dp[0][i] = 0;

  for(int i = 1; i < n + 1; ++i)

    for(int j = 1; j < n + 1; ++j)

      if(s[i - 1] == t[i - 1])

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

      else

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

  cout << dp[n][n] << endl;

}