백준 9251 - LCS (C++)

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

9251번: LCS

 

풀이

LCS는 최장 공통 부분 수열로 dp로 구현할 수 있다.

관련 포스팅은 --> https://qqs-diary.tistory.com/132

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dp[1001][1001];
char s1[1001],s2[1001];
int main()
{
    scanf("%s %s",s1+1,s2+1);
    int i=1,j=1;
    for(i=1; s1[i]; i++)
    {
        for(j=1; s2[j]; j++)
        {
            dp[i][j]=max({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]+(s1[i]==s2[j])});
        }
    }
    cout<<dp[i-1][j-1];
}