9251번: LCS

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


$O(nm)$

최장 공통 부분 수열의 길이를 구하는 문제이다.
dp[i][j]: 문자열 s1[1...i] 과 s2[1...j]의 최장 공통 부분 수열 길이
dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]+(s1[i]==s2[j]))

#include<cstdio>
#include<algorithm>
char s1[1002], s2[1002];
int dp[1001][1001], i, j;
int main() {
    scanf("%s %s", s1 + 1, s2 + 1);
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            dp[i][j] = std::max({ dp[i][j - 1],dp[i - 1][j],dp[i - 1][j - 1] + (s1[i] == s2[j]) });
    printf("%d", dp[i - 1][j - 1]);
    return 0;
}