편집 거리 (Edit Distance)

문제 설명

문자열 A를 B로 변환하는 데 필요한 최소 연산 횟수를 구하세요.

가능한 연산

• 삽입: 문자 하나 삽입
• 삭제: 문자 하나 삭제
• 교체: 문자 하나를 다른 문자로 교체

입력 형식

첫 줄: 문자열 A

둘째 줄: 문자열 B

점화식

if A[i] == B[j]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])