백준 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) }
2021. 8. 9.
