[이코테] 다이나믹 프로그래밍_편집 거리 (python) (다시 풀기)

문제

나의 풀이

1. 책 참고하여 성공

• 초기 아이디어: 삽입과 삭제가 연속되면 교체로 인정하는 코드를 짰다. 그런데.. 한계가 존재하더라.
• 그래서 결국 책을 참고하였다. 그리고 깜짝 놀람..아 이렇게 하는구나!

점화식

• 같을때 dp[i][j] = dp[i-1][j-1]
• 다를때: 열만 변화(삽입), 행만 변화(삭제), 행과 열 변화(교체)
  • dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

a, b = input(), input()

l_a, l_b = len(a), len(b)
dp = [[0] * (l_b + 1) for _ in range(l_a + 1)] # 행: 바꿀 문자, 열: 기준 문자

for i in range(l_a): # 바꿀 문자의 편집거리 초기화
    dp[i][0] = i
for j in range(l_b): # 기준 문자의 편집거리 초기화
    dp[0][j] = j


for i in range(1, l_a + 1):
    for j in range(1, l_b + 1):
        if a[i - 1] == b[j - 1]: # 문자가 같을 때 # index는 0부터 시작하니까
            dp[i][j] = dp[i-1][j-1] # 편집거리는 그대로
        else: # 문자가 다를 때
            dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1 # 편집거리는 최소값 + 1
print(dp[l_a][l_b])