백준 9251 lcs

문제 설명 :

두 문자열이 있을때 최장 공통 부분수열의 길이를 찾는 것이다.

문제 풀이 :

각각 문자열을 s, t라고 가정한다.

dp[i][j] -> Si번째부터 Tj부터 가장긴 부분 수열의 길이

조건

1 : i, j의 범위 제한
2. 기본값 세팅
3. i j가 같을 경우, i, j가 다를 경우
여기서 i,j는 s와 t의 i,j인덱스의 원소 값이다

같으면 + 1하고 i,j를 둘다 다음번째를 보면된다

다르면 둘중에 하나를 +1해서 다음껄 보고 max값을 살피면 된다

if(str1[i][j] == str2[i][j]) dp[i][j] = 1 + solve(i +1, j +1)
else {
    dp[i][j] = max(solve(i +1, j), solve(i, j+1) 
}