최장 공통 부분 수열

최장 공통 부분 수열은 LCS라고 부른다.

주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.

 

 

 

수도코드

lcs(m,n)
	for i<-0 to m
		dp[i][0] <- 0
	for j<-0 to n
		dp[0][j] <- 0
	for i<-0 to m
		for j<-0 to n
			if x[i] == y[j]
				dp[i][j] <- dp[i-1][j-1]+1;
            else
				dp[i][j] <- max(dp[i-1][j],dp[i][j-1])
	return dp[m][n]

 

 

시간 복잡도

O(NM)