(9251) LCS

https://www.acmicpc.net/problem/9251

단계별로 풀어보기

21단계(동적 계획법 1) 15번째

 

 

 

LIS만큼 유명한 LCS를 구하는 문제다.

두 문자열을 s1, s2라 하고 dp[i][j]를 s1의 1~i번째 부분문자열, s2의 1~j번째 부분문자열의 LCS라고 하자.

dp[i][j]는 기본적으로 dp[i-1][j]와 dp[i][j-1] 중 큰 값이다. 만약 s1의 i번째 글자와 s2의 j번째 글자가 같다면 LCS에 포함될 수 있고, 이때의 값은 dp[i-1][j-1]+1이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  string s1, s2;
  
  cin >> s1 >> s2;
  
  vector dp(s1.length()+1, vector<int> (s2.length()+1));
  
  for(int i=1;i<=s1.length();i++){
    for(int j=1;j<=s2.length();j++){
      dp[i][j]= max(dp[i-1][j], dp[i][j-1]);
      if(s1[i-1]==s2[j-1])  dp[i][j]= max(dp[i][j], dp[i-1][j-1]+1);
    }
  }
  
  cout << dp[s1.length()][s2.length()];
  
  return 0;
}