9251 LCS
LCS 또한 교재에서 볼 수 있는 DP의 전형적인 문제이다. 길이가 각각 i, j인 문자열 x, y가 있다고 해보자. LCS(i, j) 는 문자열 x, y의 최장 공통 부분 수열(LCS)이라고 할 때, 다음과 같이 점화식을 세울 수 있다. LCS(i, j) = LCS(i-1, j-1) + 1 if x[i] == y[j] max( LCS(i-1, j), LCS(i, j-1) ) otherwise 이렇게 만들어놓고, i와 j에 따른 dynamic programming을 구현하기 위하여 d[i][j]를 만든다. 그리고 이 행렬을 잘 채워나가다가, 맨 마지막 오른쪽 부분 즉, d[i][j]가 우리가 원하는 LSC 값이다. #include #include #include using namespace std; in..
2019. 6. 9.
