[9251] LCS

[9251] LSC : http://boj.kr/9251

### DP ###

lcs(si, ti) : 문자열 s의 si번째 문자까지, t의 ti번째의 문자까지의 가장 긴 증가하는 부분 문자열 (최장 공통 부분 수열)

#include <stdio.h>
#include <string.h>
 
char s[1001], t[1001];
int d[1001][1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lcs(int si, int ti)
{
    int ret = 0; 
 
    if(si < 0 || ti < 0) return 0;
    if(d[si][ti] != -1) return d[si][ti];
 
    if(s[si] == t[ti]) {
        ret = lcs(si-1, ti-1)+1;
    }
    else {
        ret = max(lcs(si-1, ti), lcs(si, ti-1));
    }   
    return d[si][ti] = ret;
}
 
int main()
{
    int sLen=0, tLen=0;
    scanf("%s%s", s, t);
 
    while(s[sLen]) sLen++;
    while(t[tLen]) tLen++;
 
    memset(d, -1, sizeof(d));
    printf("%d\n", lcs(sLen-1, tLen-1));
    return 0; 
}