가장 긴 공통 서브 시퀀스 재발

Question

lcs의 재발은 다음과 같습니다

L[i,j] = max(L[i-1,j], L[i,j-1]) if a[i] != a[j] 

당신은 i-1 또는 j-1 이유를 말씀해 주시겠습니까? L[i,j] = L[i-1,j-1]이 맞지 않은 이유는 무엇입니까?

Answer 1

a[i] != a[j]이 현재 두 시퀀스 A와 B를 비교하는 문자가 다른 것을 의미합니다. 따라서, 공통의 긴 시퀀스의 길이는 두 가지 중 하나 :

1. 마이너스 첫 문자 B의 현재 문자열의 긴 공통 서브 즉 L[i-1,j];
2. A의 가장 긴 공통 부분 시퀀스와 B의 현재 하위 문자열에서 첫 번째 문자를 뺀 값, 즉 L[i,j-1]. L[i-1,j-1]은 정확했다

경우는 A와 B 모두에서 현재 문자가 포함되지 않습니다 것을 의미, 그들은 서브의 일부가 될 수있는 "기회"를하지 않습니다.

예를 들어 this explanation을 참조하십시오 (역순이 아니라 연속적으로 작동한다는 점에 유의하십시오).