[알고리즘] 조건부 LCS

LCS 문제 중에서 X, Y를 비교하는데 X의 원소를 최대 k개 바꿀 수 있는 문제의 경우 다음과 같이 풀 수 있다.

def lcs(dp, arr1, n, arr2, m, k): 

  for x in range(1, k+2):
    for i in range(1, len(arr1)+1):
      for j in range(1, len(arr2)+1):
        if arr1[i-1] == arr2[j-1]:
          dp[x][i][j] = max(dp[x][i][j-1], dp[x][i-1][j], dp[x][i-1][j-1] + 1)
        else:
          dp[x][i][j] = max(dp[x][i][j-1], dp[x][i-1][j], dp[x-1][i-1][j-1] + 1)
  return dp[-1][-1][-1]
  

# Driven Program 
if __name__ == "__main__": 

  k = 1
  arr1 = "AAB" 
  arr2 = "CAB"
  n = len(arr1) 
  m = len(arr2) 

  dp = [[[0 for j in range(m+1)] for i in range(n+1)] for _ in range(k+2)] 

  print(lcs(dp, arr1, n, arr2, m, k))

 

이 로직이 핵심이다

If P[i] != Q[j], 
    dp[i][j][k] = max(dp[i - 1][j][k], 
                      dp[i][j - 1][k], 
                      dp[i - 1][j - 1][k - 1] + 1) 
If P[i] == Q[j], 
    dp[i][j][k] = max(dp[i - 1][j][k], 
                      dp[i][j - 1][k], 
                      dp[i - 1][j - 1][k] + 1)

Reference

---

https://www.geeksforgeeks.org/longest-common-subsequence-with-at-most-k-changes-allowed/

Longest Common Subsequence with at most k changes allowed - GeeksforGeeks