편집 거리 문제

삽입, 삭제, 대체 연산으로 스트링 S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소으 편집 연산 횟수

1. 부분 문제

• 접두부를 고려

• 예제

  strong을 stone으로 변화는 문제에 대해, stro를 sto로 바꾸는 편집 거리를 미리 알면, ng를 ne로 바꾸는 편집 거리를 찾음으로써 주어진 입력에 대한 편집 거리를 구할 수 있다.
  

• 점화식
  

2. 시간복잡도

• 배열을 생각하자
  O(mn)
  • n,m: 각 string의 길이